[Update 5/20/14: Feel free to borrow or adapt any part of this text for future conferences. In retrospect, perhaps I should have given some more concrete guidance: in a typical TCS paper, by page 5 or 6 you should be done with the introduction, which means that you have already clearly stated your main result, explained why it’s interesting, what are the key ideas used, and how it compares to prior works (not necessarily in that order). By page 10-15 or so, an expert should get enough information about the proof of the main result (or at least a special case that captures the main difficulty) to be fairly confident of its correctness.]
The FOCS 2014 call for papers is out. The PC chose to forgo hard page limits for submissions, trusting authors to apply their best judgment to make their submissions as easy to read and review as possible. Toward this end, here are some words of advice for potential authors. None of this is mandatory, but I hope you keep it in mind as you prepare your submission. I believe the effort to make your paper more readable will pay off not just in improving your FOCS submission, but also the future online, proceedings, and journal versions of your paper.
Remember the audience.
One of the challenging aspects of writing a FOCS submission (and in fact any scientific paper) is that it needs to address different types of readers simultaneously. A non-exhaustive list includes:
1) The expert in your field that wants to verify all the details and understand how your approach differs from their 2007 paper.
2) A non-expert reviewer that wants to understand what you did, why the question is motivated, and get some sense of the techniques you used.
3) A PC member (such as yours truly) that was not assigned to review the paper, and wants to get some approximation of the above by just skimming it for a few minutes.
A general rule of thumb for addressing those different readers is to make sure that the paper’s first few sections are accessible to a general theoretical CS audience, while later sections might contain the details that are mainly of interest to experts in the field. This brings us to our next point..
Put your best foot forward.
While there is no hard page limit, FOCS reviewers are not expected to read all submissions in full. In practice, this means you should follow what I call “Impagliazzo’s Rule”: The first X pages of the paper should make the reader want to read the next X pages, for any value of X.
In particular, you should make sure that your results, your techniques, the motivation for your work, its context and novelty compared to prior works are clearly stated early in the paper. If your main theorem is hard to state succinctly, you can state an informal version, or an important special case, adding a forward reference to the place where it’s stated in full.
The above applies not just to results but also to the techniques as well. Don’t wait until the technical section to tell us about your novel ideas. Some of the best written papers follow the introduction with a section such as “Our techniques”, “Proof outline”, “Warmup” or “Toy problem” that illustrates the ideas behind the proofs in an informal and accessible way.
While modesty is a fine virtue, you don’t want to overdo it in a FOCS submission, and hide your contributions in some remote corners of the papers. Of course, you don’t want to go too far in the other direction, and so you should also
Put your worst foot forward.
As scientists, we bend over backwards to show the potential flaws, caveats, and rooms for improvements in our work, and I expect nothing less from FOCS authors. It can be extremely frustrating for a reviewer to find out that the result is restricted in a significant way only when she reaches Section 4 of the paper. All restrictions, caveats, assumptions, and limitations should be described early in the paper. In fact, some caveats are so major that you shouldn’t wait to state them even until the introduction. For example, if you prove a lower bound that holds only for monotone circuits, then not only should this be clearly stated in the abstract, the word “monotone” should probably appear in the title. Generally speaking, if you’ve made a choice in modeling the problem that makes it easier, you should discuss this and explain what would have changed had you made a different choice. Similarly, any relations and overlap with prior works should be clearly described early in the paper. If the result is a generalization of prior work, explain how they differ and what motivates the generalization. If it improves in some parameters but is worse in others, a discussion of the significance of these is in order. If there is a related work you are aware of, even if it’s not yet formally published, or was done after your work, you should still cite it and explain the relation between the two works and the chronology.
Kill the suspense.
A scientific paper is not a novel and, ideally, readers should not be staying in suspense or be surprised negatively or positively. The FOCS PC is an incredibly talented group of people, but you should still write your paper in a “foolproof” way, trying to anticipate all questions and misunderstandings that a reader may have (especially one that needs to review 40 papers under time pressure).
For example, it can be extremely annoying for an author to get a review saying “the proof of the main theorem can be vastly simplified by using X” where X is the thing you tried first and doesn’t work. The way to avoid it is to add a section titled “First attempt” where you discuss X and explain why it fails. Similarly, if there is a paper that at first look seems related to your work, but turns out to be irrelevant, then you should still cite it and explain why it’s not actually related.
Another annoyance is when the reviews give the impression that the paper was rejected for being “too simple”. I and the rest of the FOCS PC believe that simplicity is a great virtue and never a cause for rejection. But you don’t want the reviewer to be surprised by the simplicity, discovering only late in the paper that the proof is a 3 line reduction to some prior work. If the proof is simple then be proud of this fact, and announce it right from the start. Similarly, if the proof of a particular lemma involves some routine applications of a standard method, you don’t need to remove it or move it to the appendix, but do add a sentence saying this at the proof’s start, so the less detail-oriented reviewers will know to skip ahead. This applies in the other case as well: if the proof involves a novel twist or a subtle point, you should add a sentence alerting the reader to look out for that point.
Writing a scientific paper is often a hard task, and I and the rest of the PC deeply appreciate your decision to send us your work and make the effort to communicate it as clearly as possible. We hope you find the above suggestions useful, and are looking forward to reading your submission.