Wednesday, June 16, 2010

News from Cambridge

Now that teaching has ended I plan to focus again on my P v NP book. I won't go on a full blog sabbatical, instead I'll aim to post once a week as well as keep up my tweets.

As you readers know, STOC, Complexity and EC all met last week in Cambridge, Mass. Complexity closed its registration at 140, EC broke 200 and STOC had about 350, high numbers for those conferences helped by both location and co-location. All three conferences will be part of FCRC in San Jose next year. Salil Vadhan will be PC Chair for STOC, Omer Reingold for Complexity. STOC 2012 will be held in New York City, CCC 2012 in Porto, Portugal home of Port Wine and my favorite delicacy. EC doesn't think that far ahead. 

The 2010 Gödel Prize will be awarded at ICALP to Sanjeev Arora and Joseph S.B. Mitchell for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem. 

The STOC proceedings are on-line including best student paper and best papers. The EC proceedings is also on-line with their best paper and no best student paper this year. The Complexity proceedings (published by IEEE) not on-line yet but the best student paper was The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions by Daniel Kane of Harvard. CCC didn't pick any best paper winners.

The TCS Visions are now on the CCC site, and in many more formats on Theory Mattters. Please feel free to make use of these slides to sell theory to chairs, deans, students and the general public.

At the STOC business meeting I talked about addressing the problem that STOC still only attracts a small fraction of the theory community. More on that in future posts.

Michael Schapira has a nice guest post on the EC conference and Muthu on the EC workshops. Bill promises a post on CCC tomorrow and we may have some vidcasts for you in the future.

Having CCC and EC overlap made it difficult to be a close part of either meeting. I can't believe I skipped the EC Google-subsidized Charles River Lobster Dinner cruise for the CCC business meeting but at least I got some Facebook jelly beans. I also got the HiPPo below from Ronny Kohavi's invited EC talk. The EXP stands for experiments that one should use to make choices instead of the HiPPo (Highest Paid Person's Opinion). But EXP is also a complexity class and so the hippo captures both meetings for me.


  1. Hmmm ... a quick grep of the Visions for Theoretical Computer Science discloses that science receives ample mention (52 appearances of "scien*") ... good ... and mathematics receives ample mention (19 appearances of "math*") ... also good ... and engineering gets no mention at all (zero uses of "engin*").

    Gee ... what would we think of a white paper titled "Visions for Sea Otters" that never got around to mentioning the words "kelp" and "urchins"?

    Mammologists know what that kind of of vision leads to ... namely ... a generation of starving juvenile otters!

    The converse makes better sense, because a conservation plan that focuses on kelp and urchins (and practical engineering) provides essential habitat for healthy otter populations (and healthy math and science careers).

  2. should "The EC proceedings is also on-line" be "are"?

    HiPPo should be HiPPO