STOC 50 Part II

On Wednesday, STOC had a great complexity session and the best complexity paper of the conference, Cody Murray and Ryan Williams extending Ryan’s celebrated result separating NEXP from ACC⁰. Cody and Ryan show there are problems in quasipolynomial time (2^{poly log(n)}) that do not sit in ACC⁰, a near exponential improvement from Ryan’s original work. The key insight shows that if NP has n^k-size circuits then for some j, each accepting input has a witness describable by a n^j-size circuit.

By the way everyone now has full access to the STOC Proceedings. Read and enjoy.

Before the business meeting, Moses Charikar led a panel reminiscing over the 50 years of STOC. Panelists Dick Karp, Al Borodin, Ronitt Rubinfeld and Avrim Blum talked over memories of the early conferences and the good old days of transparencies and paper submissions.

Highlights of the business meeting:

• About 350 attendees, slightly larger than years past though the organizers hoped for a larger crowd given the 50th celebration and the theory fest.
• 112 accepted papers of 416 submitted. There are now 29 PC members--time to rethink the standard in-person meeting.
• FOCS 2018 in Paris October 7-9. STOC 2019 as part of FCRC in Pheonix June 22-28. STOC 2020 likely in Copenhagen.
• New SIGACT executive committee: Samir Khuller (Chair), Eric Allender, Shuchi Chawla, Nicole Immorlica and Bobby Kleinberg.
• Shuchi Chawla taking over CATCS. Lots of goodies on the website for those applying for funding or looking for jobs.
• Sandy Irani is leading a new effort to combat harrassment in the theoretical computer science community.
• Tracy Kimbrel gave NSF report. The NSF recently appointed Rance Cleaveland as head of CCF, the division that includes algorithmic foundations. New rule: You can’t submit to both CRII and CAREER in the same year so pick your poison.