Tuesday, May 22, 2012

STOC Business Meeting

Last night I ran my last STOC business meeting as SIGACT chair. It was a three-hour affair until the hotel staff kicked us out at midnight. Lots of highlights. I put many of the slides online if you want to see details.

We had a very large turnout for STOC, over 360 participants. Being in New York definitely helped as did posters and workshop sessions. There were 90 accepted papers out of 303 submitted.

There were two best paper winners:
  • “Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds”  by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf
  • “The Cell Probe Complexity of Dynamic Range Counting,” by Kasper Green Larsen
Larsen also won the Danny Lewin best student paper award. There were three other papers considered strong enough to merit a single session talk.

Sampath Kannan won the SIGACT Distinguished Service Award for his work promoting theory at the National Science Foundation.

Both the SIGACT Distinguished Service Prize and the Knuth Award will be given annually for now because we have many excellent candidates for both. The Knuth Prize will be given in even years at FOCS and odd years at STOC.

SIGACT elections are still going on. Please vote if you are a SIGACT member and haven't done so.

Skipping ahead (so this doesn't become a three-hour post) FOCS 2012 is at Rutgers, ITCS 2013 in Berkeley, SODA 2013 in New Orleans, STOC 2013 in Palo Alto joint with Complexity and FOCS 2013 (and every two years thereafter) hosted by the new Simons Institute at Berkeley. 

2013 STOC PC chair Joan Feigenbaum described a new multi-tier structure experiment for her program committee. 

Finally László Babai led a discussion on ACM publication policies. More on that in a later post. 


  1. glad to see that concrete action plans are made. btw, the last focs business meeting at palm spring also went until around midnight. so it all seems worth it!

  2. When will the results of the SIGACT elections be known?

  3. STOC 2013 in Palo Alto joint with Complexity

    Here's hoping SoCG will join them in collocating, at least from time to time.

  4. So STOC 2013 will have a 2-tier pC, like EC? I am not sure how well it has worked for EC. Will there be a physical PC meeting?

  5. Do you have any idea about the submission deadline of ITCS 2013?


  6. Anonymous @2:39: SOCG 2013 is already planned in Rio de Janeiro. Voting for the location of SOCG 2014 will take place at the business meeting on June 17; a proposal to collocate would be welcome. Is the location of STOC 2014 known?

    Oh, wait. You're probably doing that FCRC thing again, aren't you? Yeah, that'll go over at SOCG like a lead balloon.