Skip to content

Sanjeev Arora: Potential changes to STOC/FOCS: report from special FOCS session

November 11, 2014

As Boaz advertised, FOCS had a panel-led discussion on “How might FOCS and STOC evolve?” Here is a summary of that session by Sanjeev Arora:


This blog post is a report about a special 80 min session on the future shape of STOC/FOCS, organized by David Shmoys (IEEE TCMF Chair) and Paul Beame (ACM Sigact Chair) on the Saturday before FOCS in Philadelphia. Some 100+ people attended.

The panelists: Boaz Barak, Tim Roughgarden, and me. Joan Feigenbaum couldn’t attend but sent a long email that was read aloud by David. Avi Wigderson had to cancel last minute.

For those who don’t want to read further (spoiler alert): The panelists all agreed about the need to create an annual week-long event to be held during a convenient week in summer, which would hopefully attract a larger crowd than STOC/FOCS currently do. The decision was to study how to organize such an annual event, likely starting June 2017. Now read on.

Sole ground rule from David and Paul was: no discussion of open access/copyright, nor of moving STOC/FOCS out of ACM/IEEE. (Reason: these are orthogonal to the other issues and would derail the discussion.)

Boaz and Omer’s proposal in a nutshell (details are here): Fold STOC/FOCS into this annual event. Submissions and PC work for these two would work just as now with the same timetable. Actual presentations would happen at this annual event. But the annual event would be planned by a third PC that would decide upon how much time to allocate to each paper’s presentationnot all papers would be treated equally. This PC would also plan a multi-day program of plenary talks —invited speakers, and selected papers drawn from theory conferences of the past year including STOC/FOCS. (Some people expressed discomfort with creating different classes of STOC-FOCS papers. See Boaz and Omer’s blog post for more discussion, and also my proposal below.)

Tim’s ideas: It’s very beneficial to have such a mega event in some form. Logistics may be formidable and need discussing, but it would be good for the field to have a single clearing point for major results and place to catch up with others (for which it is important that the event is attractive enough to draw everybody). His other main point: the event should give a large number of people “something to do” by which he meant “something to present.” (Could be poster presentations, talks, workshops, etc.) This helps draw people into the event rather than make them feel like bystanders.

Joan’s email: Started off by saying that we should not be afraid of experimentation. Case in point: She tried a 2-tier PC a few years ago and while many people railed against it, nobody could pinpoint any impact on the quality of the final program. She thinks STOC/FOCS currently focus too much on technical wizardry. While this has its place, other aspects should be valued as well. With this preamble, her main proposal was: There should be an inclusive annual mega event that showcases good work in many different aspects of TCS , possibly trading off some mathematical depth with inclusiveness and intellectual breadth. Secondary proposal: to fix somehow the problem of incomplete papers. (She mentioned the VLDB model where the conference is also a journal.) Interestingly, I don’t detect such a crisis in TCS today; most people post full versions on arxiv. I do support looking at the VLDB model, but for a different reason: it’s our journal process that seems broken.

My proposal: Though it was a panel discussion I prepared powerpoint slides, which are available here. My proposal has evolved from my earlier blog post which turned into a B. EATCS article. A guiding principle: “Add rather than subtract; build upon structures that already work well.” The STOC/FOCS PC process works well with efficient reviewing and decision-making—though not everybody is happy with the decisions themselves. But the journal process is sclerotic and possibly broken, so proposals (such as Fortnow’s) that replace conferences with journals seems risky. Finally, let’s design any new system to maximize buy-in from our community.

So here’s the plan in brief: Keep STOC/FOCS as now, possibly increasing the number of acceptances to 100-ish, which still fit in 3 days with 2 parallel sessions but no plenary talks. (“If you are content with your current STOC/FOCS, you don’t need to change anything.”) Then add 3-4 days of activity around STOC including workshops, poster sessions, and lots of plenary sessions. Encourage other theory conferences to co-locate with this event.

See my article and slides for further details.

A Few Meta Points that I made.

Here are a few meta points that I made, which are interrelated:

We are a part of computer science. I hope to be a realist here, not controversial. Our work involves and touches upon other disciplines: math, economics, physics, sociology, statistics, biology, operations research, etc. But most of our students will find jobs in CS departments or industrial labs, and practically none in these allied disciplines. CS is also the field (biology possibly excepted) with most growth and new jobs in the foreseeable future. Our system should be most attuned with the CS way of doing things. To shoot down an obvious straw man, we should avoid the Math mode of splitting into small sub-communities and addressing papers and research to a small group of experts. Our papers and talks should remain comprehensible and interesting for a broad TCS audience, and a significant fraction of our collective work should look interesting to a general CS audience. (Joan’s email made a similar point about the danger of what she calls “mathematization.”)

Senior people in TCS have been dropping out of the STOC/FOCS system. I am, at 46 years of age, a regular attendee, but most people my age and older aren’t. I have talked to them, and they often feel that STOC/FOCS values specialization: technical improvements to past work, and that sort of thing. Any reform should try to address their concerns, and I hope the mega event will bring them back. (My advice to these senior people: if you want to change STOC/FOCS, be willing to serve on the PC, and speak up.)

Short papers are better. There’s a strong trend towards preferring long papers with full proofs. I consider this the “Math model” because it rewards research topics and presentation aimed at a handful of experts. I favor an old-fashioned approach that’s still in fashion at top journals like Nature and Science: force authors to explain their ideas in 8 double-column pages (or some other reasonable page limit). No appendices allowed, though reviewers who need more details should be able to look up a time-stamped detailed version on arxiv. In other words, use arxiv to the fullest, but force authors to also write clean, self-contained and terse versions. This is my partial answer to the question “What is the value added by conferences?” (NB: I don’t sense a crisis of incorrect papers in STOC/FOCS right now. Plus it’s not the end of the world if a couple percent of conference papers turn out to be wrong; Science and Nature have a worse track record and are doing OK!)

Towards the end of the session David and Paul solicited further ideas from the audience. Sensing general approval of the June mega event, they announced that they will further study this idea, and possibly implement it starting 2017, without waiting for other theory conferences to collocate. Paul pointed to logistical hurdles, which necessitate careful planning. David observed that putting the spotlight on STOC may cause FOCS to wither away. Personally, I think FOCS will do fine and may even find a devoted audience of those who prefer a more intimate event.

So dear readers, please comment away with your reactions and thoughts. This issue creates strong opinions, but let’s keep it civilized. If you have a counter proposal, please put it on the web and send us the link; Paul and David are following this debate.

ps: I am skeptical of the value of anonymous comments and will tend to ignore them (and hope that the other commenters will too).


26 Comments leave one →
  1. November 11, 2014 7:47 pm

    Wait, what? The journal system is sclerotic and broken? Since when? WHY? You can’t just throw such a statement out without any justification! Possibly this is well-known and I am just ignorant, but this is honestly the first time that I’ve heard this (at least in such stark terms). Surely there are things which could be improved, but “broken”?

    • November 11, 2014 11:01 pm

      OK, I’m refering to the fact that most articles don’t appear in journals, and the total time to publication is large. (On the other hand I am told the time to publication in other fields is even more.)

      It isn’t always clear to me what people mean when they express a preference for the journal only model. The models in Math, Physics, Econ, Bio etc. are all different.

  2. Danny kale permalink
    November 12, 2014 12:16 am

    Let me express my disagreement with Sanjeev’s claims. I feel they are bent too much on social norms and utilitarian conformity rather than pure scientific grounds.

    I’ll give one example: The claim that we should distance our selves from mathematics didn’t get any explanation here. That is, why should we try to avoid “mathematization”? What is the scientific merit of this approach? If the field is turning gradually into a mathematical field, isn’t this an evidence for this route to be a natural progress of things? Should we turn things around just because they seem unfriendly? Surely, there should be scientific, not social, reasons for scientific matters.

    • November 12, 2014 1:07 am

      This post by Sanjeev is just summary. At the meeting, one reason given to avoid “mathematization” is that we (as theoretical computer scientists) have to compete with other computer scientists for jobs in computer science departments. Since the rest of computer science primarily judges research success based on the number of conference publications (in reputable conferences), it would be wise for us to continue doing this as well.

      • November 12, 2014 1:28 am

        That was reason one. The other reason is that there is a certain culture of hiring in CS depts: everybody shows up to the talk, and *expects to understand it*. This is not the culture in math depts (and probably is not feasible given how specialized it’s become over the centuries).

      • Danny Kale permalink
        November 12, 2014 7:45 pm

        Thanks for your replies. Nevertheless, I couldn’t see how you addressed my concerns. It is obvious that if we want to optimize for practical benefits like jobs, visibility (and hence funding) etc., we can simply detach ourselves from purely scientific concerns, and “sell out”, by pushing towards more friendly and approachable research goals and make our research easily understood by any CS person, or the layman.

        But one goal of academia and science is to avoid such obvious temptations. I’m not saying we should ignore practical considerations all together. I’m just pointing out that there was nothing in what was written above about the need to balance this practical approach with scientific considerations. Specifically, if there is a drift towards mathematization of the field, this drift might be well justified scientifically, and we cannot ignore this possibility, and try to divert it, based solely on practical grounds.

  3. November 12, 2014 1:23 am

    It is fine to be a mathematical field; I love beautiful proofs. But the reality is that it has to be done in CS depts and research labs. CS and Math cultures are v. different. Both have pluses and minuses.

  4. November 12, 2014 4:20 am

    Regarding 2-tier PCs:

    > She tried a 2-tier PC a few years ago and while many people railed against it, nobody could
    > pinpoint any impact on the quality of the final program. (*)

    I respectfully disagree with this statement. My experience with the STOC 2-tier experiment as a submitter was that by discouraging seeking external reviewers (and having only 2 reviewers per paper), the result was non-expert opinions for several papers and consequently some suboptimal decisions by the PC. A giant committee on the second tier is *more* likely to be able to handle a paper than a smaller committee, yes, but it’s still not likely to handle all papers “whp”. Gaps in PC expertise will still exist (and did exist in this experiment), which results in certain areas not reaping the full benefit of the expertise that the general TCS community has to offer regarding reviewing. Yes, a FOCS/STOC paper should be accessible to the broad TCS community. However, I also believe that at least one reviewer per paper should be a top expert who can easily give important feedback (“main theorem follows trivially from lemma X in paper Y”, for example, is something a non-expert would have a hard time realizing), and unless the PC has hundreds of members, some submission will be missing such a top expert.

    In summary: I think discouraging external reviewing is not a good idea. (On the contrary, I believe it should be encouraged.)

    Also note that (*) is not such great evidence. People are, for obvious reasons, very hesitant to publicly criticize the final program of a conference since the most obvious way to do that is to publicly criticize particular papers, which people shy away from.

  5. November 12, 2014 10:35 pm

    Perhaps I have a conflict of interest (as editor-in-chief of ACM Transactions on Computation Theory, and as a member of the editorial board of a few other journals, including society journals, open-access journals, and commercial journals) — but I think that it’s “risky” to dismiss the journal model entirely. I know for a fact that many papers are improved substantially, due to the efforts of conscientious referees. Although there are some examples of papers on the ArXiV or on ECCC that have similarly benefited from the commentary of readers, I believe that this happens much less frequently in that arena, than in the time-tested process of sending papers out for journal refereeing. In my own experience, I know that — although I have frequently received some valuable feedback from conference PCs — I have much more often received truly insightful comments from journal referees. (Of course, there are outliers. Some PC feedback is remarkably insightful in spite of the time pressures, and some reports from journal referees are basically worthless. But on average, the level of scrutiny that a journal paper receives seems to be significantly greater than a conference paper gets.) I expend a significant amount of effort pestering referees (and pestering editors to pester referees) to improve turn-around. And I spend a significant amount of time refereeing papers myself. The current system is certainly not perfect, but I think that it is unfair to characterize it as “broken”.

    By the way, if you’ve read this far: please consider submitting your high-quality papers to ACM Transaction on Computation Theory.

    — Eric

    • November 13, 2014 3:29 am

      Hi Eric

      I didn’t mean to dismiss journals. They have a place too. I just don’t see the obvious superiority of the “journal only” model. Please read my Bull. EATCS article for further discussion of the pros and cons.

      STOC/FOCS are actually fairly efficient ways to sort-of referee 300+ papers in fairly short time. Somehow 25-odd researchers agree to set aside a few weeks and work on this, as do hundreds of sub-reviewers. The consequence is that papers get a stamp of quality in a timely fashion, and many of our fresh PhD’s have several publications when they go on the job market. (Furthermore, the CS world expects this.) The journal system *as it currently works* is much slower, and getting 300 papers through that process would take forever.

      Every field has to figure out what works best for it; we can’t just adopt the “journal model” without asking “Which journal model? The Math one, or Physics, or Bio, or Econ, etc.” They are all different. It is conceivable there is an ideal model out there, but how do we get there from where we are right now?

      Something like the VLDB model (built on top of conferences) may well be the one that’s easiest to get to.

  6. Eric Vigoda permalink
    November 13, 2014 4:20 am

    Here is a semi-concrete proposal, a step towards the VLDB model.

    We start an IEEE journal called Foundations of Computer Science (and an ACM journal for STOC). All papers that are accepted to FOCS are automatically accepted to the journal if submitted within a reasonable time frame (say by the conference date). These are the only papers that appear in the journal. The PC members for the FOCS have to also agree to serve as associate editors for the papers in that conference. That will be at most a few papers for each PC member. The point of having PC members with this dual role is so that they can choose journal referees who did a thorough job reviewing the paper for the conference, and hopefully this will speed up and improve the process. The journal can have several issues a year, and the papers appear in the journal whenever they’re ready. The conference can still have proceedings so nothing has to change with how STOC/FOCS operate. This just gives an extra journal option for those interested. It’s kinda like an expanded sense of the special issue but in a dedicated journal for that conference.

    The benefits are that this hopefully speeds up the refereeing process a bit; it eliminates some of the hassle about preparing a journal submission — where to submit it, do I have to repackage the results, etc.; and gives people an incentive to submit their paper to a journal in a timely manner.


    • November 13, 2014 4:39 am

      I really like this proposal (except that I would have a single open access journal). I think this lets each venue do what it does best: conferences are pretty good at selecting what papers to highlight, while the journal process (when it works and is not too slow) is good in polishing the papers and verifying all details. By having papers from the conference jump straight to the “accepted pending revision” stage we can save a lot of time.

    • November 14, 2014 12:25 am

      Though I am intrigued by the VLDB model, I’m surprised that Eric or other journal editors (including Boaz) didn’t point to the obvious problem: switching to this model will impoverish the current journals. Also, going by the current speed of special conference issues, it won’t be particularly fast (especially if we’re talking about handling 100 papers instead of 10).

      Time to do a journal review is easily 10x time of a conference review. If more papers go through journal review (under current reviewing standards) we will all have to spend a lot more time reviewing.

      Personally, I think we should put more effort into getting nicely written short versions, after making sure that the details appear at an archival site. This can be done easily with the current conference reviewing system. I am not interested in 100% verification; 95-97% seems good enough.

  7. November 13, 2014 5:32 am

    Great, but I am attached to the idea of also making conference authors do an 8-page (or whatever) version for posterity. When looking at papers 10+ years old I am happiest with the conference versions; they get to point quickly and highlight ideas tersely. it is about more than just a snappy introduction.

  8. November 13, 2014 6:20 pm

    I am somewhat confused: could it not be that THE problem is with “CS hiring system” itself, not with journals? Highlighting (=advertising) newest achievements is ok, but should be taken with care: ones brain should be not ruled by “main streams”. In my eyes, the problem with CS conferences is that they have forgotten their main goal: to spread the information, not to archive the knowledge – for this last task, we still have no better way as journal publications. Here a reviewer has enough time not only to estimate the merits, but also to certify the correctness (main task of archiving). Conferences should concentrate on spreading, advertising information, on bringing people together (the main task, perhaps). And a “big meating” of FOCS/STOC folks could here be an indeed good idea.

    At the moment, “broken” seems to be not the journal system, but our view at its role.

    • November 14, 2014 12:12 am

      Indeed it is possible to conceive of a system where the best graduating PhDs have *no* publications: Econ is an example. The CS hiring system may be imperfect, but not something we can unilaterally change.

      • November 14, 2014 7:01 pm

        I fully agree with your last sentence. I only think that this our “inability to change the system” cannot be any “excuse” (or even a “certification”) for declaring journal system as “broken”. The latter is also imperfect: long delays, copyright transfer, no open access (I am not speaking about all this “open access madness”). But after ArXiv exists, these problems are almost resolved. The place of journals is now where it should be: archiving (with “correctness certificates”).

        Just conferences and journals should return to their main goals: spreed (for conferences) and archive (for journals). After this return, even the CS hiring system will change. (After years, of course, but science is patient.) My feeling is: we are trying to solve problems raised by consequences, not by wrong assumptions.

        And I fully agree with your claim “short papers are better”. Especially, for conference submissions. Detais could stay in ArXiv.

  9. Danny Kale permalink
    November 14, 2014 12:45 pm

    Re Journals vs Conferences, we should note that the publication cycle of papers in the journal model is in fact faster in average than the publication cycle in the conference model , due to low acceptance rates (approx 28%), causing most papers to be re-submitted many times to different (or same) conferences.

  10. November 15, 2014 7:54 am

    I don’t see why the 8 page version is an advantage for conferences: a journal could also require such an extended abstract in addition to the full version. This does not seem like a very hard change to make to journals.

    And I am skeptical about 95-97% accuracy check. While this may be ok for one paper but when you compose the results of several such papers, the result might be much more shaky.

  11. Watchmakers permalink
    November 15, 2014 8:57 pm

    She thinks STOC/FOCS currently focus too much on technical wizardry.

    This is a consequence of the program size being too small. When every single one of the 100 papers left to be accepted addresses an important problem we have to rely in second order signals such as how complicated is your proof. Ironically this means that the same result is likelier to be accepted with an arcane proof than a clean and clear argument.

    The process then feeds itself: most wizards get their papers published, so they become part of future program committees and in turn demand equal technical wizardry, with little attention paid to impact, elegance or applicability.

    Eventually the simple papers do not even make it to the last round, so we have PC chairs self-congratulating because they accepted “all the good papers”, not realizing that in the process they left important results by the way side. Those results had low scores and opinions from the get go because the proof turned out to be ingeniously straightforward—in hindsight only.

    • November 16, 2014 2:11 am

      Note that currently the number of accepts is closer to 70; my proposal is to increase it to about 100.

      The other issues you mention are complicated since we have no universal metric for paper quality.

      In other fields this winnowing happens in other ways. Top econ journals play a gatekeeper role similar to STOC/FOCS, except their rejection rate is higher and thus the decisions may look even more erratic.

      • Watchmakers permalink
        November 16, 2014 4:16 am

        we have no universal metric for paper quality.

        Indeed we don’t but rather to than trying to measure the many parameters of quality the current choice is to substitute quality by technical wizardry. This is a rather arbitrary choice with no rationale behind it.

      • Watchmakers permalink
        November 16, 2014 4:18 am

        As a side note, econ journals are much worse than STOC/FOCS. According to the study below most breakthroughs in Economics were rejected and ultimately did not appear in a top journal:

        How Are the Mighty Fallen: Rejected Classic Articles by Leading Economists
        Joshua S. Gans and George B. Shepherd
        The Journal of Economic Perspectives, Vol. 8, No. 1 (Winter, 1994), pp. 165-179.

        This is what hyperselectivity begets: safe, technical choices.

  12. someone permalink
    November 17, 2014 3:36 pm

    I very much like the idea of 8-page summaries. It is also useful to decide on reading the whole version or not, if needed.

    Contrary to the claims made, I think that we do have a problem with results claimed in conferences that are not falsifiable because of lack of full versions. A solution would be to request that at the time of submission the full version is available at arxiv or submitted along. If the paper is accepted to the conference, the full version should be made available somewhere as unrefereed supporting material.


  1. Turning STOC 2017 into a “Theory Festival” | Windows On Theory
  2. TheoryFest 2017 – guest post by Sanjeev Arora | 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: