This is a personal post, not representing the other members of our working group. While future discussion will naturally talk about (important) technical details such as amount of parallelism, scheduling of talks, number of days and length of breaks, I wanted to talk a bit about the broader vision. I hope other members will also post more of their thoughts in this period up to the STOC business meeting discussion.
When I was asked to chair the program of FOCS 2014, I was humbled and, frankly, somewhat worried.
The STOC and FOCS conferences have such a long and successful tradition, that my view was that a program chair can, in the best case, make an “epsilon improvement”, while there is a chance for them to screw things up pretty badly. (This is why my first decision as chair was to get a mobile app for the conference – I wanted to take care of my epsilon improvement.)
I think the secret behind the success of STOC and FOCS, as well as behind many success stories of theoretical CS, is the exchange of ideas between different areas. Take Peter Shor’s FOCS 1994 paper that ignited the field of quantum computing and caused an enormous infusion of funds and talent into it. In what other community could someone even ask the question of whether the principles of quantum mechanics could be used to factor n-bit integers in a polynomial in n amount of resources? And we don’t have to go back 20 years for such examples. One of the greatest recent advances of computer science (not just theoretical) was Craig Gentry’s STOC 2009 paper on fully homomorphic encryption. Again, the paper used techniques developed in the context of circuit complexity and worst-case/average-case reductions (as well as even quantum reductions). Even more recently, a beautiful line of works (many of which appeared in STOC/FOCS), motivated by getting faster algorithms for graph problems, used ideas from spectral graph theory, some of which was developed in coding theory and derandomization, to settle the Kadison-Singer problem – a longstanding open problem in mathematics.
But, as much as the scientific program of STOC/FOCS is strong, I believe the event itself leaves much to be desired. To some extent, this is not surprising. The program committee spends hundreds if not thousands of hours examining papers, soliciting reviews, and debating their merits to reach the final decisions. In contrast much less effort is spent in designing the schedule of the event, which often is done by the program chair on his/her own over few days. After all, there are only so many ways to squeeze 80ish 20-minute talks into two parallel sessions over three days.
Moreover, even the program itself, while excellent, cannot contain all the top works in theoretical CS. Some communities have very successful “home conferences”, whether its CRYPTO, SOCG and many more, which for many researchers are the first choice for submitting. There are also many other great theoretical works that occur in other communities, including databases, information retrieval, machine learning, coding theory, operation research, and more.
Imagine if there was a set of people whose goal was to use the selection made by the program committee to create the best experience possible for the people attending the conference. Imagine, if, via adding a day, parallelism, etc.., those people had much more flexibility in setting the schedule. Imagine if they could invite presentations on top theory works that did not appear in STOC. If they would could set an exciting plenary session where all the community gets together to hear about great recent results from broad swaths of theory, including areas not well represented by STOC/FOCS, as well as hear from exciting speakers outside theory, whether it’s top mathematicians, economists, or physicists, or researchers in systems or machine learning. Imagine if apart from that, there were also many other activities, including workshops, poster sessions, as well community-building events and events helping students and postdocs get both advice and exposure. Imagine if this event became a “must attend” event on any theorist’s calendar- a place you would go to once a year to get updated, intellectually stimulated, connect with longstanding collaborators and meet new ones. This is the kind of event we are envisioning. An event that has the STOC presentations as a crucial component, but is much more than that – a “pan theory festival”.