[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.
Summary
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.
Windows On Theory 
Please consider making FOCS/ STOC double-blind so that there is less bias from the program committee on paper decision based on author name. CRYPTO is doing that already, and one can noticeably see the difference in author/institution distributions if one compares a few years of acceptance lists.
I understand your concern about bias, and there is something very appealing about the notion of double-blind submissions, but my experience with that in CRYPTO PC’s is that it may introduce more problems that it solves, and is also becoming less relevant as online postings are more and more prevalent. As just one example, it has happened to me more than once as a CRYPTO PC member that I asked an author to review their own paper. While this is not such a big problem, it’s probably also happened that I asked people that are closely related to the author to review the paper, and if I had known about the relation I would have asked someone else, or weighed their opinion differently. (In principle, the chair can correct such issues, but there is only so much the chair can do.)
I think the differences in institution distribution between conferences have more to do with the difference in distributions of research in different areas than single vs double blind reviews.
Boaz, I think he is comparing institutions within the same conference. Certainly in SIGMOD the number of papers accepted from outside the top departments went substantially up when reviews went double blind. The same holds for various other conferences.
I believe one can trust the reviewers to follow simple obligations such as the following (after all, currently the PC is trusting the reviewers not to judge the papers by the name of authors – intentionally or unintentionally)
– Do not look up the authors’ names online
– Do not accept the review if you have seen (parts of) the submission before (and therefore you know the name of an author).
– An automated system can easily rule out the possibility of assigning a paper to someone in the same institution as one of the authors.
So I don’t see why double-blind submissions are becoming less irrelevant!
Given that reviewers are active members of the community that normally would follow papers published online in their area of research, the second requirement would basically mean that the people most qualified to review the paper are barred from doing so.
…and this is different from the current model in which way? Of the three PC members who handle your submission today you’d be lucky if more than one is familiar with the subject, unless you are working on some rather fashionable field.
I think Boaz contradicts himself here: on the one hand he says that the frequency of online postings make double blind reviews irrelevant, because publicly posted papers cannot be anonymous. On the other hand, he says that double blind reviewing causes problems because he does not know who the authors are and therefore asks the authors to review their own papers, or he asks people he would not have asked had he known the identity of the authors. Online postings do not make double blind reviewing irrelevant because authors can choose to publicly post their work AFTER it is submitted to a conference.
Also, I don’t agree with Vahid’s “rules”: A PC member (for a conference with double blind reviewing) must recuse himself from reviewing a paper when he knows who the authors are. Is that a rule for Crypto? If authors want to make their work and their authorship public, they can do so. However, in a double blind reviewing process, authors who do NOT wish to make their identity public can also do so. Therefore, the argument about having fewer available PC members to review a paper is bogus.
Double blind submissions have both advantages and disadvantages. I am not sure this is the place to debate them, especially given that the FOCS 2014 CFP is already out. (Maybe a STOC/FOCS business meeting is better forum.) My personal opinion, based on my experience as author and PC member in both types of conferences, is that the disadvantages outweigh the advantages.
What I meant by “becoming less relevant” is that the fraction of papers published online prior to submission is steadily increasing (which is a good thing! we don’t want to slow down science). I didn’t claim this fraction is 100%, and so there is no contradiction.
Modern content management systems take care of conflict resolution automatically. This is prevalent in all the top Computer Vision conferences (ICCV/ECCV/CVPR) and ML (ICML/NIPS).
I’ve been told several times in conferences that as an outsider my publications would never have reached the degree of visibility (e.g. oral) that they had, let alone be accepted, if the reviewers knew that I wasn’t part of the ‘in’ crowd. (Spoken off-the-record of course, as it’s not politically correct.)
I’ve written about this on my blog, but I really object to the philosophy you state here of:
“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).”
Amazingly enough, I’ve been fantastically surprised by the misunderstandings that PCs in general but theory PCs in particular can come up with, and I can’t possibly predict them all. Culturally, I’d rather see a bit more humility from the reviewers.
Your examples serve to help justify my point. Let’s take the first one.
“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.”
Well, there may be 10 first attempts I tried that didn’t work — and, in some cases, at least a few others I didn’t think of but really don’t work when you stop to think about them carefully. Am I really supposed to go through them all? If the reviewer REALLY think something can be vastly simplified, give a detailed explanation. Until that happens, a PC is just randomly rejecting papers that don’t meet an arbitrary criterion of convincing the reviewers that maybe there wasn’t some other way they haven’t really actually specified to solve the problem. Given that the author has except in rare circumstances thought about the problem a lot more than the reviewer, I’d tend to assume maybe the author hasn’t written about something because it doesn’t work.
Now your second example.
“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.”
The list of papers that might, to a reviewer I don’t know in advance, seem to be related but actually be irrelevant is nearly infinite. As a reviewer if you think I didn’t know about a paper that might turn out to be relevant, feel free to suggest it, but don’t expect it should be listed as part of your decision-making process. If you think a paper HAS to be cited because as an author I’ve missed something (e.g., something I’m claiming as original has already been proven), give a detailed explanation. Again, the author has thought about it a lot more than the reviewer — I’d assume that they knew about a paper and actively decided not to cite it before I’d think that I should be insisting what papers they need to cite based on my quick impression.
Perhaps instead you should say: “Theory conferences tend to overload their reviewers, and hence you should expect random, unpredictable, and sometimes downright bizarre negative comments about your papers. The reviewers didn’t have time to read them carefully, or discuss them very much. While your reviews for rejected papers might change your prior on your belief about your writing quality, they might not change them substantially; re-submit and try again, there’s every chance you’ll get luckier next time.”
This post is titled “advice for FOCS authors” and so its focus is how authors can make their papers more readable. This is not about a certain reviewing philosophy, and in fact I think most of this advice applies whether the audience is a reviewer or just any reader trying to understand it.
In contrast to a talk, the reader of a paper can’t stop you to and ask a question and so you should try to anticipate common concerns. I, and I believe others too, often find sections explaining why the obvious approach doesn’t work and pointing out various subtleties very helpful in understanding the paper. That said, these are not hard rules, and I expect authors to use their common sense rather than putting a laundry list of all the possible things that someone might raise.
I have a more positive view than yours of theory reviews, but perhaps it is because I haven’t been spoiled by the superior quality of systems conferences. However, I agree that reviewers should maintain a level of humility and it is important to keep in mind when you are reviewing that you could be wrong. This is one of the reasons why we will sometimes email authors for clarifications when a reviewer thinks they found a mistake in the paper.
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.
While you may believe so, I don’t think it generally holds. Others have alluded to this [MM, 0xDE]. But to add yet another data point, just recently we submitted a solution to a problem in a well-plodded area. The question was first asked over 20 years ago and the reviewers agreed that it was of interest. The comments were for the most part rather thoughtful and indicating depth of understanding in the field. However they included these snippets from two reviewers:
(1) “While the question here is fairly interesting, the ideas are not extremely surprising or novel. In particular, the analysis is essentially a re-use of a previous analysis”
and
(2) “although the techniques used are what I would have expected and the main contribution is simply working out the technical details”.
Who knows, the paper might have been rejected regardless because of other concerns, but it is hard to walk away from these reviews without reaching the conclusion that simplicity was seen as a minus and that if only we had found convoluted proofs the paper would have had a much higher score.
There is only so much room in any conference program and many good papers get rejected. All the hand wringing about bias, reviewing quality, etc etc does not change this simple fact.
One solution would be to increase the number of acceptances enough so that minor errors are not amplified and reviewers are not forced to split hairs to choose between amazingly good submissions, such as “solves long standing problem” and “solves long standing problem with difficulty”.
In fact, for most of their history STOC and FOCS grew along with the field. It is only in the last fifteen years that they chose to go stale and stop growing.
Today they could double the number of acceptances and still be by far the best conferences in their subfields of coverage, just like SODA grew from ~50 papers to ~130 while at the same time closing up on STOC and FOCS in various conference rankings. In fact SODA already surpassed FOCS in at least two of them. Last year’s PC chair from FOCS was open to increasing the number of acceptances going forward. I sure hope this year’s chair agrees and increases the number of papers somewhat like Omer suggested.
How will FOCS 2014 handle conflict of interest ? In all other areas, COI is treated very seriously with options to specify COI during submission. That way, reviewers with conflict of interest with a paper does not even know that such a paper exists. But it seems like in theory conferences, there is no systematic way of dealing with this issue.
We will handle conflicts in a manner similar to most other theory conferences.
PC members declare conflict of interest on papers on which they should not have any knowledge of the discussion (and I may also query them about the decision to declare or not to declare a conflict on particular paper).
In addition, all reviews will have a “conflict of interest statement” detailing the reviewer’s relation to the author/paper – since there are many relations that do not necessarily mean the person should not be part of the discussion, but that the PC would like to be aware of in order to weigh the review appropriately.