Monday, May 23, 2005

STOC Business Meeting Redux and More

My liveblogging experiment didn't quite work as planned. I seemed to have lost half of what I wrote and then my battery died. So here is some basic info from the meeting.
  • Most of the discussion was on theory funding and on the STOC republication policy and most of those discussions survived from yesterday. Check out the new Theory Matters site advocating increased theory funding.
  • The Gödel Prize went to Noga Alon, Yossi Matias and Mario Szegedy for their paper The space complexity of approximating the frequency moments.
  • Omer Reingold and Vladimir Trifonov won the best paper and best student paper awards respectively for their algorithms for undirected connectivity.
  • Future Conferences: Complexity 2005 in San Jose, California June 12-15. Early registration deadline is Friday. FOCS 2005 in Pittsburg October 23-25, STOC 2006 in Seattle May 20-23, Complexity 2006 in Prague July 16-20, STOC 2007 and Complexity 2007 as part of FCRC in San Diego June 9-16 and STOC 2008 will be in Victoria.
  • Check out the poster of the NP-completeness and the new DIMACS Implementation Challenge.
The conference had several good surveys commemorating Larry Stockmeyer who passed away last summer. Stockmeyer's advisor Albert Meyer gave a talk describing how they worked together and giving an interesting small result in Stockmeyer's thesis that certain sets created through diagonalization have i.o.-speedup. I also posted the slides and paper from my Stockmeyer lecture.

Complexity theory is well represented in this year's conference with some very nice papers in extractors, derandomization, PCP construction, hardness amplification and much more. Check out the program to see more.

On Friday and Saturday nights, the STOC hotel hosted proms from local schools. It's easier to explain baseball to non-Americans than the concept of a prom where high school students wear fancy clothes and spend large amounts of money for a single party.


  1. The TheoryMatters page has put password protection on editing of pages. I don't know if this is intended or otherwise, but it seems somewhat silly to ask for signatures on a page that can't be edited.

    Since there is no obvious 'owner' of the page, I am not even sure where to send mail. :(

  2. Sorry about this, we fixed it yesterday by adding contact information. (

    Send email to the above address (or to me) to receive the password.


  3. Actually there was almost no discussion at all on the republication policy. There should have been a special meeting devoted to the funding issue, as it was clear that there is no way to fit both this and any other important issues in one meeting.