Skip to content

Do It Yourself Theoryfestival Design – Guest Post By Sanjeev Arora

June 16, 2015

Sanjeev suggesting an interesting exercise, in our series on the design of a Theory Festival as part of STOC 2017:


Throughout our conference design process  we often observe big shifts in people’s opinions as they engage with the issues and the mathematical constraints. So if you have strong opinions about the theory festival, I highly recommend spending half an hour trying to come up with your own design.

Before and during your design, answer the following questions to yourself about the event you are planning:

  • How is the event appealing to theorists who currently don’t come?
  • How is the event creating more interaction opportunities?
  • Part of the target audience wants more signal from the PC (= more power), and part of the target audience wants to give less power to the PC because they disagree with its past decisions and general preferences. Which direction does your plan go in?

Keep in mind also the general equilibrium view:

(i) People worry about the effect of any change in the conferences on hiring/promotion/grant applications. The general equilibrium view says that if you double or halve the total number of STOC papers (“the money supply”) its only effect will be to double/halve the number of publications required to get the job or the grant. So what should determine the total number of accepts in your design?
(ii) The net attention of attendees is unchanged.  X-minute talks in 4 parallel sessions use up the same amount as X/2-minute talks in 2 parallel sessions. Which do you prefer —as author and as attendee—and why?

Of course you could argue that you can change the equilibrium by causing more jobs/grants to be created, or by increasing the number of attendees. In that case, please state your assumptions.

Have a go at it, and if you come up with interesting designs, please sketch them in your comments!



Currently: 90 accepts; 20 min talks in 2 parallel sessions (about 16-17 hrs)
Essentially no plenary. 1 separate day of workshops.

Our designs assume at least 12 plenary hrs, 2 hrs of tutorial, 1 day of workshops (all distributed over 5 days).  Plus, two hours for lunch and an evening poster session.

Remember to allow for  changeover time between speakers.

More fun at the theory festival: plenary sessions – guest post by Sanjeev Arora

June 13, 2015

Towards the business meeting, another personal post in our series (this one by Sanjeev Arora):


An important part of the plan for theory festival —which everybody involved agrees upon—is the need for a substantial plenary component. The festival organizing committee would select the plenary program based upon inputs from various sources.

Plenary sessions will include about 20-25 short talks from a broad spectrum of “Theory” subcommunities, including (but not limited to) SODA, CCC, COLT, CRYPTO, KDD, EC, PODS, PODC, etc., as well as STOC and FOCS. We envisage some kind of nomination process whereby these communities/PCs could propose recent papers presented at their recent conferences which would be of interest to a broader theory audience. Sometimes they could nominate an older paper that is now generating a lot of work, or a survey talk.

Plenary sessions would also include 1-hr lectures introducing an area in science, social science, or mathematics of interest to a broad theory audience. I could’ve generate some sample topics myself, but in interest of fun I decided to ask for suggestions from a small group of people. (I’ve reworded/shortened their answers.)

Silvio Micali: Connectomics (figuring out the graph of interconnections of the brain’s neurons from imaging data).

Scott Aaronson: (a) Recent work connecting complexity, quantum information and quantum gravity (Harlow, Hayden, Preskill etc.); it is creating waves (b) Theorist-friendly introduction to deep nets and deep learning.

Ankur Moitra: Linear Inverse Problems: recovering an object from linear measurements (includes robust PCA, matrix completion, phase retrieval, tensor completion, etc. May have interesting connections to SDPs and other convex methods studied in our community.

Suresh Venkatsubramanian: (a) Computational Topology. Motivated by data analysis, it has completely taken over what used to be called computational geometry. STOC/FOCS people might be able to provide approximation algorithms for topological quantities. (b) Optimization: a basic primitive in many applied settings, especially machine learning. Esoteric optimization ideas like momentum and regularizers are now ubiquitous in applications, but haven’t affected STOC/FOCS world much (except for recent work on flows).

In your comments, please send other suggestions for talks that might be interesting.

Remember, the festival will also have a separate slot for technical tutorials on interesting topics within CS and theoretical CS. Also, some workshops may feature their own invited/plenary talks.

STOC Festival Design: Improving interaction and fun factor; reducing information overload – guest post by Sanjeev Arora

June 10, 2015

[Yet another personal post in our series]

STOC Festival Design: Improving interaction and fun factor; reducing information overload.

Sanjeev Arora

How can we increase the value added by a conference in today’s information-rich world, when papers have been available on arxiv for months to the experts in that area?

These are some personal thoughts (ie I am not representing the committee or SIGACT).

First, I wish to make a plug for poster sessions at STOC: all papers should also be presented at an evening poster session. If you missed a talk, you can get the 2-5 min (or longer!) version at the poster session, tailored to your level of prior knowledge  and speed of comprehension.  (Remember, theory says that 2-way communication is exponentially more efficient than one-way!) Poster presenters —often students and junior researchers—will  get a chance to meet others, especially senior researchers. Ideas and email addresses will get exchanged. (Currently I talk to approximately zero students at the conference— certainly, nothing facilitates it.) Also, different coauthors could present the talk and the poster, which doubles the number of people presenting at the conference.

Second, conferences should do a better job to help us navigate today’s sea of information. (As Omer notes in his post, we can decouple the “journal of record” role of STOC with the actual program of talks.)  The current format of 95+ talks of 20 min is very fatiguing, and it is hard to figure out “What to do if my attention span only allows N talks?” Arguably, this question can be answered by the PC, but that signal is deliberately discarded and hidden from the attendees.  One way to reveal this signal would be to schedule talks of different lengths.  For example, with 130 accepts one could have 8 talks of 20 minutes in plenary sessions, 48 talks of 20 minutes in two parallel sessions, and 74 talks of 5-minutes each in two parallel sessions.  (And all papers would also be presented in poster sessions.)

Benefits: (a) Allows substantial increase in number of accepts to 130 while staying with two parallel sessions.  (b) May lead to a less risk-averse PC (ie more diverse conference) while maintaining a very high-quality core.  (c) Attendees get to tailor their consumption of content. (d) A 5-minute talk is still enough for the presenter to give a sense of the work and publicize it. Each attendee gets exposed to ½ of the overall program instead of a 1/3rd; this is efficient use of their attention span.

Possible objections: (a) Effect on tenure/promotion. (b) Noisiness of the signal (c) Authors are worse off.

I think (a) will become a non-issue. If today’s tenure case has X STOC papers, tomorrow’s might have X/2  papers with 20-min talks and X with  5-min talks (b) Yes, PCs are 100% fallible, but weigh that against all the benefits above.  If we don’t believe in PC judgement we might as well disband STOC.

For (c), let’s do quick a Pareto analysis.  The comparison plan on the table is 95 accepts: 8 plenary talks + 87 talks of 20 min in three parallel sessions. (We need three sessions because of the substantial plenary component being added.)

With 130 accepts the turnout will be higher; perhaps 25% higher. Authors are trying to maximize the number of people exposed to their paper.  The basic math is that ½ of 125% is roughly twice of 1/3rd of 100%.  We’ll see that all authors are much better off in this proposal, except those whose paper had a nominal “rank” of 57-95 in the PC process, who both gain and lose.

Rank 1-8: Somewhat better off (125% vs 100%)

Rank 9-56: Significantly better off (62% vs 33%).

Rank 57-95: Gain and lose.  (An audience of 62% instead of 33%, but 5 min talk instead of 20 min.).

Rank 96-130: Significantly better off. Their paper gets into proceedings, and they get 5 min to pique the interest of 62% of the audience (without waiting half a year to resubmit).

Every ex-PC member will tell you that papers that end up in the 3rd category were equally likely to be in the 4th, and vice versa. Knowing this, rational authors should prefer this new plan.  It makes smarter use of a scarce resource: attendees’ attention span.

Why Doesn’t ACM Have a SIG for Theoretical Computer Science? – Guest post by Moshe Vardi

June 9, 2015

[Boaz’s note – this is another in the series of personal posts on STOC/FOCS reform, this time from Moshe Vardi, a renowned theoretical computer scientist who is also the editor in chief of the communications of the ACM. See also the discussion that’s still going on in the comment section of Omer Reingold’s post, as well all discussions under this tag.]

Why Doesn’t ACM Have a SIG for Theoretical Computer Science?

Moshe Vardi

Wikipedia defines Theoretical Computer Science (TCS) as as the “division or
subset of general computer science and mathematics that focuses on more
abstract or mathematical aspects of computing.” This description of TCS
seems to be rather straightforward, and it is not clear why there should be
geographical variations in its interpretation. Yet in 1992, when Yuri
Gurevich had the opportunity to spend a few months visiting a number of
European centers of research center, he wrote in his report, titled “Logic
Activities in Europe” that “It is amazing, however, how different computer
science is, especially theoretical computer science, in Europe and the US.”
(Gurevich was preceded by E.W. Dijkstra, who wrote an EWD Note 611 “On the
fact that the Atlantic Ocean has two sides.”)

This different between TCS in the US (more generally, North America) and
Europe is often described by insiders as “Volume A” vs “Volume B”, referring
to the Handbook of Theoretical Computer Science, published in 1990, with
Jan van Leeuwen as editor. The Handbook consisted of two volumes: Volume A,
focusing on algorithms and complexity, and Volume B, focusing on formal
models and semantics. In other words, Vol. A is the theory of algorithms,
while Volume B is the theory of software. North American TCS tends to be
quite heavily Volume A, while European TCS tends to encompass both
Volume A and Volume B. Gurevich’s report was focused on on activities of
the Volume-B type, which is sometimes referred to as “Eurotheory”.

Gurevich expressed his astonishment to discover the stark different
between TCS across the two sides of the Atlantic, writing that
“The modern world is quickly growing into a global village.”
And yet the TCS gap between the US and Europe is quite sharp. To see it,
one only has to compare the programs of the North American premier TCS
conferences–IEEE Symposium on Foundations of Computer Science (FOCS)
and ACM Symposium on Theory of Computing (STOC)–with that of Europe’s
premier TCS conference, Automata, Languages, and Programming (ICALP).
In spite of its somewhat anachronistic name, ICALP today has three tracks
with quite a broad coverage.

How did such a sharp division arose between TCS in North America and Europe?
This division did not exist prior to the 1980s. In fact, the tables of
content of the proceedings of FOCS and STOC from the 1970s reveal an
surprisingly (from today’s perspective) high level of Volume-B content. In
the 1980s, the level of TCS activities in North America grew beyond the
capacity of two annual single-track three-day conferences, which led to the
launching of what was known then as “satellite conferences”. Having shed
“satellite” topics, allowed FOCS and STOC to specialize, developing a
narrower focus on TCS. But the narrow focus of STOC and FOCS, the two
premier North American conferences, in turn has influenced what is
considered TCS in North America.

It is astonishing therefore to realize that the turn “Eurotheory” is
used somewhat derogatorily, implying a narrow and esoteric focus for
European TCS. From my perch as Editor-in-Chief for Communications, today’s
spectrum of TCS is vastly broader than what is revealed in the programs of
FOCS and STOC. The issue is no longer Volume A vs Volume B or Northern
America vs Europe (or other emerging centers of TCS around the world),
but rather the broadening gap between the narrow focus of FOCS and STOC
and the broadening scope of TCS. It is symptomatic indeed that unlike
the European Association for Theoretical Computer Science, ACM has no
Special Interest Group (SIG) for TCS. ACM does have SIGACT, a Special
Interest Group for Algorithms and Complexity Theory, but its narrow focus
is already revealed in its name [Paul Beame comments below that SIGACT stands for “Algorithms and Computation Theory” -B.].

This discussion is not of sociological interest only. The North
American TCS community has been discussing over the past few years
possible changes to the current way of running its two conferences,
considering folding FOCS and STOC into a single annual conference of
longer duration. A May 2015 blog entry by Boaz Barak is titled “Turning
STOC 2017 into a ‘Theory Festival'”. The proposal is focused on changing
the conference from the standard recitation of fast-paced research talks,
to a richer scientific event, with invited talks, workshops and tutorials,
social activities, poster and rump session, and the like.

I like very much the proposed directions for FOCS/STOC, but I’d also like to
see the North American TCS community show a deeper level of reflectiveness
on the narrowing of their research agenda, starting with the question posed
in the title of this editorial: Why doesn’t ACM have a SIG for Theoretical
Computer Science?

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.



Get every new post delivered to your Inbox.

Join 305 other followers