Tuesday, November 24, 2009

DIMACS at 20

Last Friday DIMACS celebrated its 20th anniversary. Muthu summarizes the event.

DIMACS has served the theoretical computer science community well over these two decades. They have hosted a number of postdocs and visitors usually around a Special Focus (originally Special years but one year is usually not enough). DIMACS runs a large number of educational and research activities but most importantly the great workshops over the years. DIMACS's reputation for having strong workshops allows it to continue to attract strong workshops and has helped make New Jersey (my home state) a major center of theory. 

The first DIMACS workshop I attended, Structural Complexity and Cryptography is where I first heard about about the first Gödel-prize winning research relating interactive proofs to hardness of approximation that was done primarily during that Special Year on Complexity Theory and Interactive Computation.

When I moved to the NEC Research Institute in 1999, I became quite active in DIMACS which had then started a Special Year on Computational Intractability including a great workshop on the Intrinsic Complexity of Computations with many great talks and discussions on the hardness of proving lower bounds. My talk on Diagonalization later became an article in the BEATCS complexity column.

I then joined the DIMACS executive board as the NEC representative just as the center was ending its 11-years of funding as an NSF Science and Technology Center. Amazing that DIMACS survived that transition and survived for these twenty years and beyond. Most of the credit goes to DIMACS director Fred Roberts who has often hustled for funding for specific special foci, projects and workshops, as well as finding people to run those foci and workshops.

The 2001 Workshop on Computational Issues in Game Theory and Mechanism Design truly established a new discipline in connecting computer science and economic theory. Based on the excitement from that workshop, DIMACS started a Special Focus on Computation and the Socio-Economic Sciences which Fred talked me into co-organizing with Rakesh Vohra, from Northwestern's Kellogg business school. After I moved back to Chicago in 2003, I met with Rakesh to plan the focus which led to collaboration and eventually my moving to Northwestern. 

The special focus had a number of exciting workshops particularly Information Markets which restarted that research area a couple years after the PAM disaster and our closing workshop on the Boundary between Economic Theory and Computer Science one of the few meetings that truly attracted both strong computer scientists and economists.

That's just a few of my DIMACS memories. Many others have similar stories for a center that helped shape the professional lives of myself and many other CS researchers. Congrats for 20 years and here's hoping for many more.

1 comment:

  1. I had a great time as an IAS-DIMACS postdoc. And, the first conference I attended was a DIMACS Workshop on "Random Graphs and Randomized Algorithms" organized by Milena Mihail and Joel Spencer, in 9/91.

    I have fond memories of my association with this wonderful institution. I could deepen my understanding of extractors, approx. alg.s, and correlation inequalities during my time there.

    Happy next 20, DIMACS!