Skip to content

Can We Get Serious?

June 8, 2015

This post represents my personal opinion (and only my opinion) with respect to turning STOC 2017 into a “Theory Festival.”

FOCS and STOC is where the entire theory community is supposed to come together for the benefit of the fruitful exchange of ideas between sub-areas of theory (which as Boaz mentioned, has been one of the sources of the community’s success). But this beautiful vision is threatened by two growing trends to worry about:

  1. More and more researchers in specific sub-communities abandon FOCS and STOC for the benefit of specialized venues that provide more effective exposure to their work.
  2. Even the FOCS-STOC experience gets fragmented as people tend to attend talks in areas closer to their own research (it is hard to know what to attend out of so many talks outside of one’s area).

The second issue could be addressed with a strong plenary program that would focus the attention of the entire community. This does not seem to be controversial and so I believe that STOC 2017 will have such a program, which is great. The second issue is much more problematic. We can no longer expect all of the strongest work in theory to be submitted to FOCS/STOC and I would think that having strong specialized venues should be encouraged. It is therefore difficult to expect researchers from area X that was “lost to FOCS/STOC” to attend the event just for the FOCS/STOC papers. In my mind, the only way to get them back is to offer a strong program in area X in addition to the plenary program that would allow them to stay connected with other areas of theory. This will require some effort and does not come for free as it will reduce the centrality of FOCS/STOC talks within the more general event. So this is the place to ask: are we really serious about a pan-theory event or are we content with keeping FOCS/STOC a place where a fraction of the theory community meets? Are we serious enough to give up a little bit of our entitled attention?

Currently, a large group of good intentioned individuals, led by the SIGACT executive committee, is considering designs for STOC 2017. This group is trying to be as attentive as possible to the voices coming out of the entire community. The problem is that in such a committee work it is very tempting to go for a conservative small change that will not upset anyone (but may gain too little). As the set of reasonable constraints and goals is impossible to completely satisfy, it is tempting to concentrate on not losing anything STOC already is rather than on gaining something new for the sake of what STOC can become. Being a romantic, I wish there was a hope to be just a little bit bolder!

To be less vague, let me conclude with the design of a pan-theory event that I would have chosen. This would be an event that would be more attractive for me to attend and much more attractive for researcher from the areas of theory that are underserved by STOC:

A STOC PC will select its program as usual (but with full flexibility regarding the number of accepted papers). An organizing committee will design the program of the theory festival. This committee will have representatives from the STOC PC but also from many other subareas of theory. The program will have three parts:

  1. A plenary session designed by the organizing committee and aimed to present only what the entire community should hear about.
  2. An afternoon session in many parallel tracks containing a collection of 3-5 days workshops (featuring STOC papers as well as other papers). These workshops will be curated by the organizing committee. For natural areas (various Algorithms areas, Complexity, ML, Econ, Cryptography, Quantum Computing, etc) representatives of the organizing committee will be setting up a workshop program (as they would do for an Oberwolfach/Simons/Banf … workshop). The committee can also accept other workshop proposals.
  3. An evening session that will include poster sessions (having guaranteed spots for all STOC papers).

The main challenge I see is to allocate a venue with many rooms for the parallel sessions. STOC papers will get a little bit less “formal attention” but will probably get on average more “substantial attention.” In particular, papers that deserve the attention of the entire community will be presented in the plenary session, while other papers will get the attention of their respective subcommunity (as they currently do). In addition, the poster session will give a more relaxed and interactive forum for cross-area interactions.

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

Cryptography Program@Simons: Historical Papers

May 30, 2015

The cryptography program at Simons is well under way and we’re wrapping up our second week here at the wonderful Simons Institute at Berkeley. It’s been a roller-coaster ride discussing the thrilling developments in the field: from fully homomorphic encryption to multilinear maps, obfuscation, differential privacy and more. The orientation/bootcamp week was an unqualified success: survey talks are online and can be viewed on the program webpage. Many thanks to the speakers and organizers.

I wanted to highlight another aspect of the program, which I’m also very excited about. Vinod Vaikuntanathan and Daniel Wichs are organizing a weekly “historical papers seminar series” for the program. This series will consist of talks about seminal papers that had, and continue to have, long-lasting impact in cryptography and beyond. The talks will discuss not only the work itself but also its historical context and more broadly how the field has evolved, and where the techniques found applications both in and out of cryptography.

The series will start next week on Wednesday June 3 with a talk by Ron Rivest “on the growth of cryptography” (see details below). The talk is intended for a broad audience, so drop by if you’re in the vicinity. We also plan to video all the talks and have them available on the program website.

Title:         On the growth of cryptography
Speaker:   Ronald L. Rivest, Vannevar Bush Professor, MIT
Date:         Wednesday, June 3rd at  2 – 3:30 pm

This talk gives a broad overview of the growth of cryptography, emphasizing some of the now “historical” aspects the speaker was involved in, such as RSA, MD5, RC4, and so on.  The talk is intended for a broad audience.


Turning STOC 2017 into a “Theory Festival”

May 7, 2015

This blog post seeks to solicit input from the theoretical CS community on possible changes to STOC starting 2017. This planning was set in motion as a result of a long discussion session at FOCS 2014 (see these two earlier posts) when strong support was expressed for a longer “theory festival” that would include STOC but have have other events, and broader appeal.

The SIGACT executive committee has asked us (Sanjeev, Boaz, Piotr, Omer and Tim) to prepare suggestions for the scope and shape of such an event, which we will present in the STOC 2015 business meeting. We welcome your input, either as comments below or as email to the address theoryfestival at We are also studying conference structures in other research communities, and soliciting opinions directly from many individuals.

Main consideration: What role should STOC play these days, now that papers are electronically available many months before the conference? Perhaps the focus should be on promoting network effects. Exchange of ideas between sub-communities is an important feature of theoretical CS, and one of the main reasons for holding a “big-tent” conference in the first place. An event with a bigger menu of activities to pick and choose, as well as a strong plenary component, could serve a variety of audiences and bring together people from different subfields, potentially increasing attendance. This means papers get more exposure; and attendees have a higher probability of connecting with colleagues, all of which make the conference even more attractive, thus creating a virtuous cycle.

What kind of activities might such a “theory festival” contain above and beyond a typical STOC? Some options are:

  1. Plenary talks: In recent STOC/FOCS’s there has been very little room for them; which is a waste of a rare opportunity when broad swaths of the theory community get together. Such plenary talks could contain:a) “Outward looking talks” by leading researchers in adjacent fields, whether it’s other parts of computer science or other sciences such as mathematics, physics, biology or economics.

    b) “Inward looking talks” by leading theoretical computer scientists that can survey for the audience recent advances in some area of TCS. (Recent STOC/FOCS’s have sometimes contained such talks, but often very few of them.)

    c) Presentation of recent technical work, whether it is from the current conference (where typically these days only the best paper awardees are presented in a plenary session) or top papers from other theory conferences.

  2. Workshops/tutorials: Recent FOCS/STOC have had a day of these, but it would be good include more “mini workshops”, ranging from a couple hours to a full day. Researchers often have many time and travel budget constraints which sometimes preclude them from going to a broad conference such as STOC/FOCS where only a tiny fraction of the talks will be in their immediate area. Having a specialized workshop as part of it might make it more appealing, promote information exchange within subcommunities and allow subcommunities to present their most important work in a polished form to the STOC attendees.
  3. Social activities: These bring the community together and help researchers of different sub-fields, geographical areas, and seniority levels get to know one another. Currently, STOC/FOCS have little room for these.
  4. Poster session, rump session, etc.: Poster sessions (consisting of papers selected by the PC) are an important part of conferences such as NIPS. They present information in a way that makes it possible to interactively browse through a vast menu, and ability to determine the quantum of time and attention (whether 2, 5 or 10 minutes) to devote to each. Poster sessions have had limited impact on theory conferences so far but this could easily change. If poster sessions were selected by the PC, they would attract better papers, which in turn would draw a bigger audience, which in turn would attract even better papers. Poster sessions could also give smaller sub-communities within theoretical CS a more permanent place at STOC, instead of being represented by a couple of papers.

We’ve been tossing around some of the above ideas, but we would love to hear more suggestions for other activities and content that could make the conference more attractive for you.

Alas, even if STOC expands to 5 or 6 days, it may not be possible to fit everything without some tradeoffs. So it is important to us to learn which tradeoffs are acceptable to you. Possible approaches to get more flexibility in scheduling include:

  1. More parallelism – moving from 2 parallel sessions to 3 parallel sessions for those talks that are not scheduled in the plenary session. (Note however that if there is 50% growth in attendance then each talk could still get the same visibility. In addition, accepted papers could be presented in evening poster sessions.)
  2. Paper presentations of varying lengths. Some papers presented at plenary sessions; others presented in shorter talks (possibly accompanied by poster presentation), as is done at NIPS. One can also have a “fast forward session” (as at SIGGRAPH) where authors give pointers to look for in the parallel sessions.  Experimenting with different talk for a brief presentation of their paper (aka “advertisement talk”) so that people know which formats might be a good idea regardless of schedule constraints — we have become very used to the standard format of a 20 minute talk in 2 parallel sessions, but there may be other ways to facilitate an exchange of ideas, and enable participants to get samples from areas of research outside their own.
  3. The default mode presentation mode for most STOC papers could be as a poster presentation together with a 3-5 minute “advertisement talk”. A subset of papers would be selected for the plenary session (which would, as mentioned above, feature also TCS papers from other conferences).  Other papers might be presented as part of the specialized workshops and tutorials.

What do you think? What would make you more likely to go to STOC? What changes could turn your off? Please do comment below.

Two requests: First, we prefer signed comments, but if you must comment anonymously, please include some information on your research area, country where you work, and your current academic status (e.g., student, faculty, postdoc etc..) and any other pertinent information. One of our goals is to understand whether STOC/FOCS serve some populations better than others.  Second, please make no comments about open access and copyright issues, or issues such as conferences vs journals,  as those are beyond the purview of this working group that is focused on making STOC a better event for the people that attend it.

We will monitor these comments until the STOC 2015 business meeting where we hope to hear from you in person. We are looking forward to your input!

Sanjeev Arora, Boaz Barak, Piotr Indyk, Omer Reingold and Tim Roughgarden

DIMACS looking for an associate director

April 14, 2015

The DIMACS Center at Rutgers University ( is seeking an Associate Director. DIMACS facilitates research, education, and outreach in discrete mathematics, computer science theory, algorithms, mathematical and statistical methods, and their applications.  The Associate Director is expected to play a leadership role in planning, developing, and running DIMACS activities and programs, including setting new directions.  A PhD in computer science, mathematics, operations research, statistics, or a related field is preferred. Applicants with a doctorate will be considered for Associate Director with a non-tenure-track calendar-year research faculty appointment at Rutgers. Highly qualified applicants without a doctorate will be considered for a staff appointment as Assistant Director. For more details, visit

2015 Swedish Summer School in Computer Science – apply soon

March 25, 2015

Last summer I gave a mini-course on the Sum of Squares algorithm in the Swedish Summer School of Computer Science.

It was a great experience – the venue was  Djurönäset  – a hotel in the beautiful Stockholm archipelgo with stunning views and great food. It was organized very smoothly by Jakob Nordström, Per Austrin, and Johan Håstad, andthe students were bright and enthusiastic. I could see them collaborating on homework problems well into the night, and I’m sure that beyond learning on theoretical computer science, they made great new connections.

In fact, I believe the only downside to that summer school was my own course – this was the first time I taught  this material and so it felt very much like a beta version. (On the other hand, Ryan O’Donnell gave a fantastic lecture series on analysis of Boolean function, so the students didn’t suffer too much.) Luckily, this year the summer school features two absolute top experts on coding theory, Venkat Guruswami and Sergey Yekhanin, who will give courses on developments that are not yet as widely known in the theoretical computer science community as they should be, but have had wide reaching impact. Polar codes are considered one of the great recent breakthroughs in coding theory as they provide in some sense the first explicit codes that achieve Shannon’s non-constructive bounds for the capacity of the binary symmetric channel. Codes with local decoding are a prime example of the surprising interplay between theory and practice. Originally arising from probabilistically checkable proofs, they have recently found very significant industrial applications,  saving companies 100’s of millions of dollars.

I hear that there are still a few slots left. If you are a Ph.D student, Masters student, or postdoc who want to know more about coding theory, I can hardly think of a more pleasant and beneficial way to do so. If you are interested, please apply as soon as possible at . For any questions, the organizers can be contacted at

NSF mandates (sort of) open access

March 24, 2015

See here.

NSF-sponsored papers should be freely available no more than 12 months after publication in a journal.

This is not perfect, but a step in the right direction. Computer scientists should insist that conference proceedings are treated the same way, and made freely available no more than 12 months after publication.

Hat tip: Lance Fortnow.


Get every new post delivered to your Inbox.

Join 301 other followers