STOC 2016

I attended the 2016 STOC Conference earlier this week in Cambridge, Massachusetts. No shortage of awesome results highlighted by László Babai's new quasipolynomial-time graph isomorphism algorithm. Babai didn't have a chance to give more than a glimpse into his algorithm in the 20 minute talk but you did see his joy in discovering the concept of "affected" last September, the key to making the whole algorithm work.

Babai also received the ACM SIGACT Distinguished Service prize for his work for the community including his open-access journal Theory of Computing.

You can see and access all the papers from the program page. Links on that page will give you free access to the papers forever. I'll mention some papers here but you'll have to click over on the program page to access them.

Troy Lee gave my favorite talk on his paper Separations in Query Complexity Based on Pointer Functions with Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Miklos Santha and Juris Smotrovs. He gave a wonderful description of a (contrived) function that gives strong separations between deterministic, randomized and quantum decision tree complexity. Scott Aaronson, Shalev Ben-David and Robin Kothari followed up on that work in Separations in query complexity using cheat sheets. 

Let me also mention the best paper winners

• Reed-Muller Codes Achieve Capacity on Erasure Channels by Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu and Rudiger Urbanke
• Explicit Two-Source Extractors and Resilient Functions by Eshan Chattopadhyay and David Zuckerman
• Graph Isomorphism in Quasipolynomial Time by Laszlo Babai

and the Danny Lewin best student paper awardees

• A Tight Space Bound for Consensus by Leqi Zhu
• The 4/3 Additive Spanner Exponent is Tight by Amir Abboud and Greg Bodwin

The conference had 327 registrants, 44% students and 74% from the USA. The Symposium on Computational Geometry was held at Tufts before STOC and they held a joint workshop day in between. There were about 20 registered for both conferences.

STOC had 92 accepted papers out of 370 submissions. None of the three papers claiming to settle P v NP were accepted.

STOC 2017 will be held in Montreal June 19-23, the first of a theory festival. There will be multiple day poster sessions, a poster for every papers. Invited talks will included best papers from other theory conference. There will be a mild increase in the number of accepted papers. The hope is to draw a broader and larger group of theorists for this festival.

The first STOC conference was held in Marina del Rey in 1969. That makes the 2018 conference STOC's 50th which will return to Southern California. The Conference on Computational Complexity will co-locate.

FOCS 2016 will be held October 9-11 in New Brunswick, New Jersey preceded by a celebration for the 60th birthday for Avi Wigderson.

SODA 2017 will be held January 16-19 in Barcelona. Paper registration deadline is July 6.

If you weren't at the business meeting, it's worth looking at the slides for the NSF and the Committee for the Advancement for Theoretical Computer Science. Of particular note, the CATCS site Theory Matters has job announcements and sample CAREER proposals.