(Amit Chakrabarti reports from Atlanta on FOCS 2009)

The FOCS 2009 programme proper begins tomorrow. Today, at Georgia Tech, we listened to four hour-long talks by distinguished researchers, celebrating the 50th anniversary of FOCS and the 20th of the university’s ACO program.

  1. We heard Dick Karp talk about what makes an algorithm “great”. The talk surveyed many of the significant milestones in our ongoing journey of discovery. In passing, he mentioned a number of (mostly recently-developed) subareas he didn’t get to dwell upon, one of which was “streaming algorithms”.
  2. Mihalis Yannakakis spoke about the computational aspects of finding equilibria, and the related issues of local search algorithms and convergence. The SQUARE-ROOT-SUM problem made an appearance, as did a joke about the throwing-overboard of Hippasus.
  3. Noga Alon talked about isoperimetric inequalities and their applications in algorithms (focussing on the DISJOINT-PATHS problem) and combinatorics (focussing on finding economical toric spines). Noga recalled publishing his first FOCS paper exactly 25 years ago, and thanked 21 of the 25 PCs since then for treating well his many submissions. He consulted his notes to list the four exceptions. This was easily the most technical of today’s talks. Noga even apologized for this mid-talk, to my surprise (doesn’t this community enjoy the technical details?).
  4. Rounding out the day was a talk by Manuel Blum who hardly talked TCS (as we know it) at all, focussing instead of the deeply philosophical matter of the definition of consciousness. He did not provide an attempt at a crisp answer, but instead gave five vignettes, one of which introduced us to Global Workspace Theory. This talk was unlike any we are used to hearing from a computer scientist. Though it did not suggest any research directions to me, it had the stimulating effect of a good Borges short.

Over dinner, I couldn’t help but comment to my companions on what I wished I’d heard today: What were the controversies in the field 20, 30, 40 years ago? I’m sure the more senior among us could regale us with tales that make the Conceptual Wars of today seem tame!