Friday, February 20, 2009

FOCS 2009

Sorry for not blogging. It's not that I've been busy -- it's more like incredibly busy.

Anyway, the FOCS 2009 call for papers seems to be out. Following are the key changes in the call.

Pre-submission abstracts: are out. As I said before, I am against them.


Full proofs: are required for the "central claims in the paper." Essentially, you don't need to prove that 3rd extension of your results that nobody will care about, but you need to write a complete proof of the main result (i.e. the really interesting result for which the paper is being accepted). When SODA'09 introduced this, my gut feeling was slightly against, but with time as a good advisor, I have become a convert. I am glad I managed to push this into the call (it was harder than I had expected...)

Here are excerpts from mails that I wrote on this topic:

[...] It happens too often that people submit a paper vague enough that an interested reviewer cannot even refute (how can you give counter-examples to something that is not fully specified in the paper?). Obviously, the job of conferences is not to check correctness, but if we get lucky with a passionate reviewer, we should allow him to do the job right.

[...] PCmember makes a valid point that the committee can (and should) ask for clarifications when a proof is missing or unclear. But this does not rule out the following scenario:

" Lemmas 13 to 15 don't have proofs in the paper. The reviewers never themselves thought about the problem, and the lemmas appear quite reasonable and straight-forward, so no objection is raised (no need to bother the author for a technicality). After the paper is published, somebody who has thought about the problem reads the proof and has doubts about Lemma 14. What now? "

The paper should be verifiable not only by the committee (whose emails the author will certainly not ignore!) but also by future readers (imagine the authors' response time if the future reader is a guy with a funny name from China :).


I hope asking for complete proofs becomes standard. As with journals, the main reason to trust the proof is not that somebody else formally checked it, but that the author carefully wrote down a detailed proof.


Post-submission description: This is the biggest innovation in the call. You are supposed to write a 2-page description of your paper one week after the deadline, in which you informally describe the contribution, the main ideas etc.

I am very sorry that this made it. To be blunt, I think the two main reasons this idea made it were:


  1. Some people thought something is "wrong" with current STOC/FOCS and something should be changed. People didn't quite have a consistent story of what was wrong or what should be changed, but the desire of change made the PC agree with the most radical experiment on the table.

  2. There was no vote (almost nobody responded to a request for a vote). I have no idea whether 75% of the PC supports this, or a vocal 20% of the PC supported it. An unfortunate state of fact.

My formal objection was the following (several people agreed in private emails):

Essentially, we can make the conference system as complicated as we want: pre-submission abstracts, double blind, 2-page summary, video at time of submission, rebuttals, a million rules for conflicts of interest etc etc. Some field which obsess about some central conference implement some subset of these ideas (think SIGGRAPH, SIGCOMM etc). Fortunately, in theory we have avoided all this non-sense.

We are implementing the basic systems principle: keep the interface simple. The process is minimal (submit a paper, get a decision and reviews). Since we have a fast turn-around cycle (with two major conferences a year, plus other reasonable conferences like SODA), there is no need to "bullet-proof" one conference. Any mistake by a PC should be rectified by the next one if the author clears up the misunderstandings in his paper.

What would the 2-page abstract do? It would force me to cut some arbitrary part of my introduction (I typically have around 4 pages). Why impose this 2 page fixed format for what should be the introduction?

Also, the 2-page abstracts would sanction the idea that a foggy introduction written at the last minute is ok, since you can rectify it 1 week later. -- Yes, yes, we threated that we may not read the 2-page abstract, but that is also wrong. If we actually don't read it, we seem like the evil PC that just wants to keep authors busy for no good reason. And any argument that "thinking about your contribution 1 week later is good for you" is as annoying as any paternalistic argument.

Theory has a light-weight process centered on ideas. Anything else should be minimized. Let's keep it simple.


To be clear, everybody seemed to agree that the 2-page description is only an experiment, and future PCs should not borrow it without serious review. I hope it will die after this conference.

13 comments:

Anonymous said...

I'm not sure whether the post-submission summary is supposed to be more like an edited-to-size copy of the introduction or more like one of the blog posts that the more shamelessly self-promotional of us write about our own papers, but either way I don't see the point. If you haven't already said the same things clearly enough in your real introduction, why should you be given a second chance?

I do like the requirement for complete proofs of main results, though. Along with what you write about this part (which I agree with) these also have the advantage of forcing the author to write out the full version ahead of time, making it a little more likely that they'll submit it for an archival journal version afterwards.

Anonymous said...

What the CFP asks for in this 2-page bit is what almost everyone seemed to know 15-20 years ago should be the introduction when they submitted their papers: A successful conference submission should be written differently from a final paper: The first two pages should be an introduction that makes your case for the paper (and explains what you did) because there is no guarantee that anyone will have time to read beyond them. Typically, final versions should have toned down introductions.

Some of the constraints that fostered this have gone by the wayside: The pile of printed papers used to arrive in a box so it was much more difficult to farm them out to sub-reviewers around the world. This meant that reviewers without multiple nearby colleagues did a lot of reading completely on their own. Nowadays, asking sub-reviewers is easy, and authors, who are getting detailed reviews and may not realize the importance of their intros, seem much more sure that their full ten pages will actually be read by someone. It is possible that they don't even realize the value of it.

Another reason for the change is that there was definitely a backlash against egregious over-selling in the introductions of some papers. This meant that hype is a little out of style.

At some level the requirement is simply "write a decent intro". I personally am not a big fan of the requirement but being after the full submission I don't think it is likely to be too detrimental to try it.

Anonymous said...

I like the full proofs requirement.

I'm not so sure about the "central claims" qualification. First, there is the obvious issue of who decides which claims are central. I assume that the rule will be, roughly, that if a reviewer wanted to verify something and no proof was provided, then you have broken the rule, and confidence in your submission's correctness will go down.

What actually bothers me more is that often the "3rd extensions" are exactly what is interesting some years later, in follow-up work. If you make a vague claim and provide no proof, then no one can ever publish a paper on the topic, unless they prove you wrong. So the claim goes on existing forever with no real verification.

So I would prefer to see more precise language in the call for papers; roughly: every explicit proposition, lemma, claim theorem should be accompanied by a proof (unless it is simple enough that it can be verified easily-- not just believed-- by a reader on their own).

Mihai said...

Adam, I certainly agree that the 3rd extension can be interesting down the road. But you have to balance this with the interest of getting something out the door quickly.

The paper would probably be accepted without the 3rd extension. So do you want the author to submit it without mentioning the extension? Hiding information is always bad. He's pointing out something interesting that can be done, and potentially saving a young graduate student some effort.

But the problem that you mention is real, of course. Mikkel Thorup has proposed (quite seriously...) that claims without proofs should expire in a few years. If you don't have a journal version in 3 years, it should be up for grabs and anybody should be able to publish a proof that you did not include.

Anonymous said...

It's interesting that you admit that people in the US would likely take a long time or not respond at all to a question from someone in China, but you don't think that this same discrimination necessitates double blind reviewing.

We discriminate. Let's have anonymous submissions.

Mihai said...

Anon, if you read the last part of my post you will understand exactly why I disapprove of double blind.

It's one thing not responding to email from China and India (I get many questions which are on average very silly), it's another to assume the PC will not carefully read the paper if they don't know the author. That is not true.

Anonymous said...

MiP Said:
Mikkel Thorup has proposed (quite seriously...) that claims without proofs should expire in a few years. If you don't have a journal version in 3 years, it should be up for grabs and anybody should be able to publish a proof that you did not include.

I like this idea; it is good to give incentives for journalizing papers.

Unfortunately, journals are sometimes quite slow, 3 years may not be enough.

Anonymous said...

"Mikkel Thorup has proposed (quite seriously...) that claims without proofs should expire in a few years."

I don't understand this statement. Suppose someone proves a theorem and you see how to use this theorem in one of your results. You write to the author to ask for a full version of their paper with a proof of that theorem. If they don't have it, and then you spend sometime trying to prove it yourself, you can publish it in your paper and simply state that the authors did not provide a proof of their theorem, so you are providing one here.

Jelani Nelson said...

So do you want the author to submit it without mentioning the extension? Hiding information is always bad.

Without a proof for all we know it might be false information, in which case hiding it would be preferable. Anyways, often times a proof sketch would suffice to convince someone the theorem statement is true -- an author could at least include that. If some proof sketches don't fit in the conference version, put details on arXiv.

Anonymous said...

I don't have problems with having all proofs (or all "important" proofs) in the submission, but why is it then called an *extended abstract*?

Anonymous said...

claims without proofs should expire in a few years.

I first heard of this quite a few years ago at Dagstuhl. A group of researchers had "re-proven" a long standing claim for which no hint of the proof had appeared nearly ten years after first being claimed. Still, their result kept getting rejected because "it wasn't new". Eventually they had to engage in personal non-standard interactions with the PC chair and Editors to get the paper published.

The idea of proofs expiring in ten years was mentioned then as a bit of a lark, but those present (which included quite a few editors) quickly agreed and suggested no more than five years begiven to any non-trivial claim lacking public proof (e.g. arxiving the long version would secure your result).

Since papers are peer reviewed (that's us) all we need to do is start applying this rule when refereeing to make it a reality.

Interestingly math already operates in this mode, and quite seamlessly so. When it became clear that the full details of Grisha's proof of the Poincare conjecture where not forthcoming, the filling in of the gaps was immediately declared open and several groups published papers on this.

Since Grisha gave a more or less complete outline, the result is still considered his, but the people who filled in the details will get well deserved citations in reward for their housekeeping efforts.

Anonymous said...

If they don't have it, and then you spend sometime trying to prove it yourself, you can publish it in your paper and simply state that the authors did not provide a proof of their theorem, so you are providing one here.

That's the way it ought to be. In practice it doesn't quite work that way. In particular it is very difficult to prove that a very incomplete proof is wrong if the few details given belong to an actual correct proof (for one, you cannot give counterexamples).

Unknown said...

Anon wrote:
Unfortunately, journals are sometimes quite slow, 3 years may not be enough

This doesn't really matter nowadays. We have arXiv, personal web pages, and online technical reports that allow an author to distribute the full proof as soon as it's done.