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.