Monday, June 28, 2004

Don't Make it Too Easy or Too Much

Two easy ways to improve your paper but lessen your chances of acceptance at a conference: Add more results and simplify your proofs. Adding a result could only increase the usefulness of a paper but program committees see many results in a paper and conclude that none of them could be very strong. One of our students a few years ago had a paper rejected at STOC, he removed one of his two main theorems and won the best student paper award at FOCS.

Given the same theorem, the community benefits from a simple proof over a complicated proof. Program committees look for hard results so if they see a very simple proof, it can count against you.

You need to play the game. If you have many results depending on the situation, you can either split the paper or highlight one result and bury the others. It's a bit unethical to use a hard proof where you know an easy one but many people make an easy proof look harder by adding an unnecessary level of detail or proving a more general but less interesting theorem.

You do what you need to do, within ethical standards, to get your paper accepted. After you get it accepted, remember you have a rewrite for a proceedings version to get the paper written the way it should.

1. Had a long comment: decided to make it a post. More here

2. I'm not so sure that simple proofs add that much value. A more complex proof, while being overkill for one application, might be exactly the tool someone else needs for an even *more* difficult proof. It's better to have difficult proofs along with the simpler versions, so it seems to be wise to keep the difficult one around, just to add something more to everyone else's toolbox.

Now, I'm not sure that's what's going on in reviewer's heads, but sometimes we do the right thing for the wrong reasons.

3. Trying to tailor your paper for acceptance for STOC/FOCS is a gamble, since you don't know who's going to be on the PC and who's going to review your paper. So, it's better just to write it the best way you can, and if a good paper is rejected simply resubmit to the next STOC/FOCS which will have a different PC.

Anecdotal examples such as the ones you mention tend to stick in memory, but that doesn't mean that they indicate a good strategy for acceptance. In particular, if I'm reviewing the paper and I get the feeling that the proof is unnecessarily complicated then that tends to make me quite annoyed. If there's an apperantly obvoius approach to proving and the paper doesn't take it then I'd like the authors to explain in a paragraph what are the pitfalls of that approach.

Boaz Barak

4. Sorry - You *do* know who's on the PC, but you usually don't know how they review papers, and many times the paper will be given to an external referee. --Boaz

5. I have to agree with Boaz: let's not infer too many general principles from one (albeit amusing) anecdote. There is no reason to believe that the removal of one result was what made it a better paper. It probably was better written with better insight the second time around. Maybe it was more in sync with the PC's tastes, who knows?

In an ideal world, the PC will have papers reviewed by people who are familiar enough with the precise area to tell the difference between a slick proof and a trivial result, a hard proof and a silly one buried under technical complications. Encouraging obfuscation is not the solution.

6. I think what Lance said was taken too seriously and too literally.

Here is the main issue in my view:
You have a result with a complicated proof.
Should you work more to try and simplify it,
or try to work on something else.
This is a real dilemma, which come up often.
(Complicated proofs are easier to come by.)

It seems that almost everyone that commented agrees
that it is better to work on something new than to simplify something "old". This is an unfortunate point of view, but definitely dominates given how PC select papers.

7. Not to sound too wise/idealistic.. But, acceptance and rejection to "certain" conferences should not govern too much how one should choose to present a result. Ofcourse, one should use discretion where to send what paper..

Staying in touch with the perspective is important. Why are we doing it? To satisfy our curiosity. For our self fullfillment. Let 95% of the satisfaction come from knowing the unknown one is after.. And, let the rest 5% of the satisfaction be from sharing it with the community instead of throwing the result in the dustbin after knowing it! :-)

While sharing it with the community one should do the best job one can.. If one deems the technique, irrespective of how complex it is, that one comes up with, may be of interest to others or useful or conceptualization interesting, so be it. If not then the simplest is obviously the best. STOC or STACS, worst or best - labels; Labels are though labels. So, just enjoy yourself :-)

SV