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