What's the expected level of paper to be submitted to top level conferences in theoretical computer science (FOCS/SODA/STOC)?

I think there should be four main concern:

  1. Is it a novel results?
  2. How hard is the paper?
  3. Generality and extension of the results.
  4. Is it an interesting topic?

But actually I cannot imagine how reviewers are going to measure above concerns, e.g, If in some paper there is 10 mediocre result means is good? ...., also I don't know is there any other important thing that we should be careful about it for top conferences.

Actually someone can try to send the paper to the FOCS/SODA/STOC and see if is rejected then send it to some other conferences, but IMHO this is not appreciated. It's good if referees to related conferences help to understand what did they expecting for top conferences?

P.S1: Actually one of an important things in all the conferences is writing style, but suppose all preliminary stuffs like writing are OK.

P.S2: I could talk about this with my adviser, but also it's very appreciated to see other top conferences reviewers/participants/... opinion about this.

P.S3: Also experience of reviewers in similar fields would be very appreciated.


2 Answers 2


What's the expected level of paper to be submitted to top level conferences in theoritical computer science (FOCS/SODA/STOC)?

Top. The top level.

My experience on program committees for STOC, FOCS, ITCS, SODA, SOCG, etc., is that there are FAR more submissions of publishable quality than can be accepted into the conference. By "publishable quality" I mean a well-written presentation of a novel, interesting, and non-trivial result within the scope of the conference.

For example, I was on the STOC 2013 program committee. We accepted 99 out of 361 submissions. Program committee members were specifically instructed to limit the top rating to only the top 20% of the papers we reviewed; at least for me, that meant some very hard choices. Most of the discussion in the last week of the review cycle revolved around papers that were clearly very strong, but were not obviously "competitive" with other papers that were already accepted.

There are several questions that come up over and over in the FOCS/STOC review cycle:

  • How surprising / novel / elegant / interesting is the result?
  • How surprising / novel / elegant / interesting / general are the techniques?
  • How technically difficult is the result? Ironically, FOCS and STOC committees have a reputation for ignoring the distinction between trivial (easy to derive from scratch) and nondeterministically trivial (easy to understand after the fact).
  • What is the expected impact of this result? Is this paper going to change the way people do theoretical computer science over the next five years?
  • Is the result of general interest to the theoretical computer science community? Or is it only of interest to a narrow subcommunity? In particular, if the topic is outside the STOC/FOCS mainstream—say, for example, computational topology—does the paper do a good job of explaining and motivating the results to a typical STOC/FOCS audience?

As a general rule, for a paper to be accepted to STOC/FOCS, at least one person on the program committee must be willing to pound on the table and demand that the paper is accepted, with strong answers to all these questions. Which means that as a minimum, the authors must have compelling answers to all these questions, even if professional modesty forbids writing those answers into the paper.

Specific criteria vary between different conferences, and not only because of the obvious differences in topical coverage. A well-written paper that combines existing techniques is a surprising way to obtain an elegant proof of a novel and interesting result, but does not introduce new techniques or require much technical sophistication, is much more likely to be accepted at SODA than at STOC or FOCS. (I've seen more than one paper rejected from STOC and accepted to SODA with precisely that review summary at both conferences.) ITCS favors conceptual contributions — new approaches, new models, new problem areas — over technical difficulty.

But at its core, conference reviewing is a random process. (As Baruch Awerbuch put it: "...whose expectation depends on the submissions, and whose variance depends on the program committee.") Every submission is a gamble. Your chances of winning the lottery may be small, but they're infinitely larger if you actually buy a ticket than if you don't.

  • Write the best papers you can.
  • Keep your target audience in mind when you write.
  • Especially if you're submitting to a conference for the first time, get feedback on your paper from a community expert well before you submit.
  • If you believe you have a reasonable chance of acceptance, submit it. Be respectful but brutally honest with yourself. Do not listen to the Impostor Syndrome.
  • Regardless of the outcome, take reviews and other feedback seriously. Don't just revise your paper; also revise your writing habits and your mental model of the audience for future submissions.
  • Rejection is not the end of the world. It's only one paper; you'll write dozens more.

Actually someone can try to send the paper to the FOCS/SODA/STOC and see if is rejected then send it to some other conferences, but IMHO this is not appreciated.

It's a bit more subtle than that. Submitting a paper that might get in is fine. What PCs really don't like is being asked to review submissions that are clearly below threshold, especially papers that were previously submitted to comparable conferences but were not updated to respond to previous reviews. (Even when a paper is submitted to several different conferences, it's not uncommon to have overlapping sets of reviewers. I've been asked to review four different submissions of the same paper.)


When I review a paper for a conference or a journal, this is how I answer these questions:

Is it a novel results?

Do I know something equivalent? Do the authors make a good job to compare their approach with related work? Is the difference with related work important enough?

How hard is the paper?

It depends on what you mean by "hard". If I read a paper where everything seems obvious/trivial, then I might question the actual contribution of the paper (and I'm talking about obvious/trivial here, i.e., where every result in the paper does need any justification). Of course, a paper can be extremely simple and elegant, and be a very powerful contribution.
On the other hand, if I can't understand the results of the paper, then I'm probably not the right reviewer for this paper.

Generality and extension of the results.

Can I reuse the results of the paper for something else? Are the simplifications/assumptions of the authors reasonable?

Is it an interesting topic?

Did the authors make a good case to motivate their contribution? Am I personally interested in this topic?

There are of course many other aspects to take into account. Personally, the only difference I make when reviewing a paper for a top-conference compared to a small workshop, is that in the latter case, I understand that "the authors leave that aspect for future work" more often. The other different is the threshold: for FOCS 2012, 169 papers were rejected. So, if I classify a paper as a "weak accept" for a small workshop, it might passes, whereas the competition might be much tougher for a top-conference.

Just write the best paper you possibly can within the deadline, and don't think "hum, this level should be enough": if you can improve it, do so!

  • 6
    If it's trivial, then it might not be that novel, — If you don't distinguish between hard to understand and hard to discover, you must believe that P=NP. What are you, some kind of crank?
    – JeffE
    May 1, 2013 at 15:55
  • @JeffE: As a general rule of thumb for the kind of papers I usually review, if the proof of a theorem is trivial, then it's likely to be a reformulation of an existing result. A result can be simple and extremely interesting, but trivial results might not bring much as such. However, it's not a strict rule, it's just that if a paper is like "here is a model, here is a theorem on this model, the proof of which is trivial", then I might be suspicious.
    – user102
    May 1, 2013 at 16:10
  • 1
    @JeffE I have edited my question to reflect this point.
    – user102
    May 1, 2013 at 16:17
  • Thank you very much for nice response, I also will wait for the other responses few days. (if is there any other one who want to contribute). May 1, 2013 at 16:35
  • @SaeedAmiri: I'm glad you get an answer from JeffE, his experience is extremely valuable for your question!
    – user102
    May 1, 2013 at 22:56

Not the answer you're looking for? Browse other questions tagged .