Skip to content

Imagining a theory festival – a personal post

June 6, 2015

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”.

8 Comments leave one →
  1. June 7, 2015 9:11 pm

    I think that a single event would be very convenient. FCRC seems the closest thing that we have right now, and I generally prefer attending two conferences there back to back (as in fact I’ll do next week) rather than traveling twice. However I find a bit disconcerting the idea that there should be a disconnect between the papers that are worth STOC/FOCS and those that are worth the audience time.

    • June 8, 2015 2:42 am

      While Omer and I advocated merging the events for STOC and FOCS, it seems there are various logistical difficulties with this, as well as with other co-location, so at the moment our focus is on co-locating STOC with many other activities that are not conferences.

      I am not sure what you mean by a “disconnect” – perhaps this refers to the suggestion that some papers get only poster presentations or very short talks. This was only one of many ideas floated, and I do not think is necessary to create a great event. What is probably necessary is to increase the amount of parallelism, but I believe that the increased number of attendees and the increased fraction of them that finds something appealing at any given time slot will more than make for that, and on average, the amount of attention each paper gets will only grow.

      • June 9, 2015 1:42 pm

        I am not sure if this is also only one of many ideas floated, but I thought that one goal was to reduce the number of travels, also for people with family constraints. However if we don’t co-locate or take other measures in that direction, but instead add a “must attend” event, then I guess that goal is not on the table? Or perhaps the plan is to duplicate talks so that someone could just go to the mega event. But that may be problematic too. First, the speakers have to travel more, and historically at least they are a big fraction of the attendees. And also it may be hard to make it a must attend event if we still have independent conferences that people working in the area will probably want to attend.

      • June 9, 2015 9:35 pm

        Omer and I did suggest to merge STOC and FOCS exactly to reduce travel, and I still hope eventually there would be co location.

        At the moment there seem to be issues with that, so we’re talking about extending STOC (so at least not adding an event but rather changing one that already exists).

  2. June 9, 2015 10:16 pm

    Boaz, you wrote “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. ”

    Why do we need a new set of people, let alone imagining one, when it is (or should be) precisely the job of the PC to form such a program? that is, “set [up] an exciting plenary session where all the community gets together to hear about great recent results” from the theory of computation (leaving things beyond it to individual choices). Setting up such a session is a sufficiently challenging task, why make it even harder by asking such a committee to make “must attend” choices that transcend its expertise?

    And in addition, we can have “also many other activities, including workshops, poster sessions, as well community-building events and events helping students and postdocs get both advice and exposure.” These can take place in parallel sessions, and can be partially based on a selection from the same pool of submissions (or from separate pools designated for that).

    • June 10, 2015 2:38 am

      The point is that to design a program that represents recent progress across all of theory you need to also include papers that were not submitted to STOC.

      • June 10, 2015 7:16 am

        What do you meant by “all of theory”? If this is all of TOC (theory of computation), then this is covered by FOCS/STOC and papers in that area (esp those with a broad appeal) are regularly submitted to FOCS/STOC. Are you talking about the very rare cases in which such papers are not submitted???

        I think we better focus on TOC per se and on the papers submitted.
        The point is that the PCs are not doing their job, since they don’t understand what their job is. Their job is exactly what you now imagine. It is to put together an “exciting plenary session where all the community gets together to hear about great recent results” [and/or directions and/or ideas].
        (In addition, it should also create several specialized parallel session that present good works that are of interest mainly for experts — see more below.) And authors should present their work accordingly — that is, trying to address the TOC community at large and not merely the experts.

        The PC need *not* assign the same amount of time to all presentations in the plenary session. It should consider what is most “cost effective” on a paper by paper basis: for some papers the community at large need only hear the result and its contents, for others a presentation of some ideas that underlie the result may be beneficial.

        Re the specialize sessions. They can be formed out of two sources:
        1. Submissions not selected for the plenary session;
        2. Submission designated for the specialized session only.
        Details are to be worked out. But one has to agree on the vision first.


  1. Can We Get Serious? | Windows On Theory

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: