This is a good example of how STOC/FOCS have grown significantly in quality over the years. Savitch's theorem was in STOC 1969, and the proof is trivial.The proof of Savitch's theorem is easy (trivial is a little strong) but the result was surprising at the time and has had a profound impact on complexity since. I'd love to see STOC and FOCS have results this easy and this important.
I had mentioned before that an easy proof can hurt your chances of acceptance at a conference. Let's take a look at the viewpoint of the program committee.
If you have a previously established hard theorem, one that many people have worked on but no proofs or only complicated proofs have been found, then short proofs are valued. Dinur's proof of the PCP theorem fits in this category. A simple proof of the parallel repetition theorem or the unique games conjecture would also be welcome in STOC or FOCS.
But most papers at STOC and FOCS do not solve previously established hard theorems. They extend previous work, improve bounds or make partial progress towards the major open questions. The program committee has to decide whether the result represents real progress or it just easily follows from previous work. An easy proof gives an indication of the latter.
Unfortunately this gives an incentive for the authors to make their proofs look difficult in their papers. A quick way for a PC member to kill a paper is to show an easy proof but the committee doesn't have the time to try and find easy proofs for all the submissions.
Probably even a 1-paragraph proof of the Unique Games Conjecture would be welcome in STOC/FOCS.
ReplyDeleteSpeaking of 2-prover 1-round games, maybe a program committee can combat this problem by having half of its reviewers read just the statements of the papers' theorems, and half of the reviewers read the proofs.
What about hiring committees? Do you think they also tend to prefer complicated proofs?
ReplyDeleteThere has been alot of comments in
ReplyDeletethis weblog about what STOC and FOCS
do or have a reputation for doing.
Has anyone done a systematic study of this
(I doubt it.) I would be very curious to
have some of the factual issues understood
before we complain. Annecdotal evidence
an only take you so far.
Questions:
Do they REALLY have a bias against Simple
proofs?
Have things REALLY gotten better?
How much does being in a HOT FIELD matter?
I don't expect answers to these questions,
but realize that the response
``Simple proofs get rejected because
So-and-so's paper was turned down''
does not add much to the debate.
Nor does
``If So-and-so was submitted now it
would be turned down.''
How to study the issue?
Getting a list of simple results that
were ACCEPTED would be easy, though
time consuming (hmmm- who defines easy?)
Getting a list of simple and important
results that were turned down would be
much harder.
It seems, then, that the following is the best strategy:
ReplyDelete1. Submit a complicated proof of your result. Assuming the result is interesting, it will be accepted because it looks nontrivial.
2. In next year's FOCS or STOC, submit the short proof of your result. It will be accepted because it provides a short proof of a theorem thought to be nontrivial.
Jeff seems to suggest that
ReplyDeletethere is a distinction between
"simple" and "easy" proofs and that
can be consistently recognized.
Is it so clear?
What about an easy proof that
everyone has missed but the theorem
is really good. Sometimes
stating a theorem in a right way
or generalizing it enough makes it
much more useful and interesting.
The proof might be implicit in
a special case. Is the proof then
easy or simple? There are no
clear cut answers to these questions.
The PC tries to figure out all
this messy stuff and makes a
decision. Unless there are systematic inconsistencies or
biases that can be seen via
some kind of reasonable data
analysis, there is no point in
quibbling over a few decisions
here and there. STOC/FOCS papers
are not ends in themselves. Too
much navel gazing can be harmful!
Go prove a nice theorem (and give
a simple proof if you can).
STOC/FOCS papers are not ends in themselves.
ReplyDeleteAh, but to many of us still trying to establish our careers, they are.
The explanation has been repeated time and time again: hiring committees and grant committees with little background in our field ask, "what are the best conferences in this field?" and then "how many papers has this candidate had accepted to these conferences?" At that point, their decision is 90% made.
What I find baffling is that some with well-established careers continue to submit to STOC/FOCS. Presumably, these people don't need the CV-padding nearly as much as fledgling theorists. Hence, they have the power to dilute the "holy grail" factor that is STOC/FOCS.
The ancient greek mathematicians had proofs that are no less involved than this generation's longest, and yet how many people apart from historians of mathematics (there is such a profession) remember them? On the other hand, how many of you remember the proof that the square root of two is irrational, or the proof that there are infinitely many prime numbers?
ReplyDeleteThe moral of the story? If you want to go for the long-term, go for the simple proof.
I think the distinction is between an argument like Savitch's algorithm and an argument like Cantor's diagonalization. They both have very simple proofs, but Cantor's is actually mind-altering. The first time you encounter it in life, you're like woah...
ReplyDeleteAlso, the undecidability of Halting problem seems fairly easy, given Goedel's work, and of course Cantor's, before it. It's still vitally important to know, too.
ReplyDeleteWhen I'm a PC member, if a paper has a complex proof, and there's a natural simpler approach, I expect an explanation why this approach doesn't work. It does not help the paper's chances if I suspect that it does.
ReplyDeleteOf course it is hard for the authors to predict all simplifying approaches the PC will think of, but they are expected to invest time in simplifying the proofs.
From my viewpoint (coming from crypto...) the most important thing is what the paper solves: if it solves an important open problem, it's great. If the solution is simple/elegant/efficient then it's even greater. If the problem is not open but very important and the paper gives a simpler and/or more elegant and/or more efficient solution than the previous solution, it's almost as great. Getting "complicated proofs" is orthogonal, and partial harmful, to the goal. I remember an urban story about math students in the Moscow State University, who competed in producing as complicated proofs as possible for already solved problems.
ReplyDelete-- ``Simple proofs get rejected because So-and-so's paper was turned down'' does not add much to the debate.
ReplyDeleteSure, on the other hand a few of the people who post here regularly serve in program committees including STOC/FOCS/SODA/SOCG/CCC/etc. While this not as exhaustive as the study you suggest, at least for those people their sample space reaches beyond that of individual rejected papers.
Lance,
ReplyDeletePlease comment also on the value STOC/FOCS gives to people from unknown places, and no reputation of publishing papers. Consider, a situation when a Ramanujam-kind-of-guy gives a bad presentation, possibly with unknown-and-unnecessary notation, of a very simple proof which is original.
Has there been a case when these conferences accepted such papers?