Posted by: jonkatz | March 5, 2010

What STOC/FOCS should (could?) be

(It’s been observed that posts with technical content get no comments, while “controversial” posts get more, so here goes…)

Michael Mitzenmacher encourages the theory community to figure out what STOC/FOCS should be, while David Karger suggests that STOC/FOCS should accept more applied results. Though I love applications of theory to problems in other areas, I find myself disagreeing with Karger and thinking almost exactly the opposite.

Here’s one radical proposal, that would have the effect of making the “STOC/FOCS experience” simultaneously more and less competitive, while also (I think) attracting more people and making the conferences themselves more relevant.

The idea is to have STOC/FOCS contain only those results of broad appeal and sufficient importance to the TCS community at large, interpreted stringently. I.e., these should be the papers that everyone in the community should be reading. I think this is the intent of STOC/FOCS anyway, but this intent has been lost by accepting too many papers. As others have so often complained, STOC/FOCS has become a “vanity” conference, driven by fads, where technically strong papers solving (sometimes) problems of marginal interest often appear. That is not to say these papers aren’t good, or aren’t important in their respective subfields. All I am questioning is whether they are of interest to the TCS community at large, instead of just being of interest to some smaller sub-community.

Can we find 60 papers, twice a year, that reach this high bar? Probably not. So let’s cut the number of papers accepted. Maybe have one day of talks, with no parallel sessions (so everyone could actually attend all the talks). Moreover, I would suggest accepting fewer papers if it is judged that there weren’t enough submissions of broad enough interest. For the purposes of this post, let’s refer to this 1-day conference as SF1.

But wouldn’t this make STOC/FOCS even more competitive than it is now? Yes…and (paradoxically) no. On the one hand, getting a paper into SF1 would a great achievement, and much more difficult. On the other hand, there would no longer be the expectation (read: pressure) of graduating with 4-5 STOC/FOCS publications just to have a chance on the job market, or of trying to maintain the pace of publishing several STOC/FOCS papers per year. Moreover, there would be several “SF2” tracks where people could publish, as I describe next.

Surely people won’t attend a one-day conference where they don’t even have a paper to present. So let’s add 2-3 days of conferences in specialized areas. (Think FCRC, but on a smaller scale.) Whatever community wants one could have one, and we could call it SF2:Algorithms, SF2:Crypto, etc.. Papers could be submitted to SF1, and considered for the appropriate track of SF2 if they are rejected from SF1. Within SF2, papers would be judged by their interest to the appropriate community (as they are now for SODA, Crypto, etc.) rather than a TCS-wide standard. Seems to me a win-win.

Let me summarize what I see as the benefits of this approach:

  • Would highlight to the TCS community what are the important papers that everyone should be reading. Would foster a sense of community among TCS researchers. Would highlight to the broader CS community what are the breakthroughs in theory.
  • Would increase attendance: everyone would want to attend SF1, and once there would also attend the SF2 in their area.
  • Would reduce some of the pressure related to STOC/FOCS, because (1) it wouldn’t be expected to have many SF1 publications, while (2) it would be easier to have an SF2 publication than it is to get into STOC/FOCS now.




  1. That’s absolutely brilliant! I’d further suggest that submission to FOCS/STOC be “by invitation only”. That is, everyone still submits their best results to the respective area conferences, and then the respective PC nominates a couple papers to a central PC (with representatives from each PC) and then they fight it out.

    This has a number of advantages:

    (1) The “best papers” for each area is no longer determined by the select (and subjective view of) 1-3 representatives from the area, but instead, by a larger expert community.

    [This also means that the representatives on the FOCS/STOC PC should be allowed to submit.]

    (2) For researchers, there’s no longer the issue of “should I risk FOCS/STOC and having to wait?”

    (3) I can’t help but notice that there’s been a couple of recent FOCS/STOCs where there’s a dismal number of crypto papers. (This is an argument that applies to any other area.) It’s hard to tell whether it’s the case that crypto people on the PC are not fighting for crypto papers, or that the crypto submissions are simply not up to par. With the nomination system, at least we can decouple the issues and reduce the effect of the “personality factor”.

  2. This actually seems to make sense.

    Which pretty much guarantees it will never get done. 😦

  3. Let me try to play devil’s advocate and try to present the other side of the coin.

    Given # STOC/FOCS papers are a primary metric for judging theory candidates,
    I am not sure having STOC/FOCS accept paper only with broad appeal would be a good idea. This would discourage deep research in specialized (but nonetheless very important) topics. Examples of such topics are abundantly available in crypto – we don’t have to go very far.

    I think if the community doesn’t place too much value in SF1 papers, this suggestion could work. For this reason, I think having paper in SF1 only by invitation sound like an interesting idea.

  4. It sounds quite reasonable basically, but I wonder: are there really such results that “appeal to the TCS community at large” these days?

    For example, which are papers from STOC/FOCS of the last five years that should be read by everybody in the community (or even the community being restricted to “American theory”)?

    I guess the standard is either too high or too controversial for the proposal to happen in reality.

    After all, people are vain; and there is no way to avoid the current situation.

  5. Along the same lines, I recall hearing someone suggest that one of FOCS/STOC should halve the number of papers it accepts, and the other one should double it.

  6. This is pretty brilliant!
    I strongly support this new stoc/focs format.

  7. I guess you were writing this post mostly as a joke. But if the humor is lost on some readers (as it seems to be), I recommend the following exercise: write down a list of 5-10 papers that would qualify from the recent STOC.

  8. It probably makes more sense to have SF1 devoted to a single paper, SF2 devoted to two papers, SF3 devoted to four, etc.

    This way, you would need exponentially fewer reviewers for the most relevant and important papers.

  9. Excellent idea–I support you heartily

  10. I like the idea. NIPS is a bit similar. A very small number of papers are accepted for oral presentation, and then a large number of papers are accepted for poster presentation. Moreover, all papers appear in the same proceedings. The result, as you suggest, is that people are not expected to have oral presentations, and it is not embarrassing to have a paper at the poster session. Quite the opposite is true — the poster sessions are very lively.

  11. In response to those (noname, Mihai) who have suggested that there are not enough papers to fill SF1, I think this only makes the argument stronger.

    If STOC/FOCS is not about papers that the whole community should be reading, then what is it?

    I’m also completely ok with accepting fewer papers to SF1, and allowing people to talk longer than 25 minutes about important results.

  12. There are definitely enough papers. It requires a broad mind to see them (ahem, Mihai), but a good scientist should be broad-minded.

    I disagree that the number of accepted papers should be reduced. Instead, the acceptance decision should be based more heavily on whether the paper makes addresses its argument to the broad TCS audience. The point of FOCS/STOC should be to bring the TCS community together, not to poach the most technical papers from other conferences.

  13. I was on a STOC/FOCS PC some years ago that split the papers, with some in single session (including both student award papers and other papers) and some in parallel sessions. The idea was to include the most broadly appealing/accessible papers, though not necessarily what we saw as “the best”, in the single session.
    This seems similar to what is proposed here.

    The bottom line is that in retrospect we were not very good at making this categorization. Some papers that had been accessible on submission ended up improved but less accessible in the final version. There were many that we missed from the rest that would have been more broadly interesting (even at the time) and have turned subsequently out to be much more important. I don’t think that we are that good in deciding which of two good papers is likely to be more widely appealing.

    I also don’t like the assumption about how to deal with the remaining papers. I don’t believe that one can just pigeonhole the other papers in one of a few predetermined categories.

  14. Paul, thanks for the perspective.

    I don’t claim that any PC can perfectly predict which papers will be of broadest interest and which will not. (And the answer will, just like all PC decisions, be partly subjective anyway.) But I see too many papers (half?) in STOC/FOCS that are clearly *not* of broad interest.

  15. I completely agree with the view that the conferences should accept fewer papers.

    But my point (and question which you don’t answer) is “what are those few?”.

    For me, there seems to be simply none. If somebody picks up to 5 papers, say, then the choice would be too controversial. It might make sense if STOC/FOCS are held once in several years like ICM.

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s


%d bloggers like this: