All too often theoretical computer scientists get more obsessed by proofs than the theorems themselves. I suggest a theorems conference. Here's how it would work:
Authors would submit two versions of a paper. One has the statement of the theorem and why that theorem matters, but no proofs. The second version includes the proofs.
The program committee first makes tentative decisions based on the first version of the paper. If tentatively accepted the PC then looks at the second version. The PC can reject the paper if the the proofs have significant flaws, gaps or readability issues. The PC cannot reject the paper for any other aspect of the proof such as length or lack of technical depth or originality.
This way we truly judge papers based on what they prove--what the results add to the knowledge base of the field.
Of course my plan has many flaws. Some papers with their proofs may have already been posted on archive sites which the PC members could have seen. More likely, the PC will guess the difficulty of the proof and judge the paper based on this perceived difficulty, and not on the theorem itself.
We need a culture shift, away from an emphasis on proofs. That's the only way we can judge our results for the results themselves.
Why insist on a culture shift in the first place? Results are important, but by looking at proofs we can judge a paper not only on its difficulty (real or perceived), but also on its contribution to the toolkit of the field. For instance, introduction of a new method, of a new way of combining known methods,etc.
ReplyDeleteAgreeing with Pascal. Particularly in my field (algorithms), it happens that the proofs are much more important than the theorems itself, since they contribute new techniques, tookits, insight, ...
ReplyDeleteIronically Pascal and Anonymous confirm the need for this conference. They completely forget that the statement of the theorem itself adds to the toolkit. For example, Hopcroft-Karp perfect matching algorithm is used as a blackbox in many sophisticated follow up results.
ReplyDeletep.s. We recently ran into this problem ourselves. We first solved a version of the graph partitioning problem under a narrow definition of overlap using new techniques and published this result. Later on, we then managed to generalize the theorem to a broad set of measures of overlap, essentially making the theorem itself the valuable contribution to the toolkit. So long as your measure has some basic natural properties you can apply the theorem.
ReplyDeleteSadly, some of the referees couldn't get past the fact that the proof was a just a careful reworking of the original much smaller result. Review after review pointed out that the proof wasn't too sophisticated. Not one mentioned that the theorem was broad and of high impact, in spite of half a dozen explicit examples of actual applications which are now possible under the more general form.
I really like this suggestion, but imo all (or at least most) conferences and journals should be like The Theorems Conference, the pc should judge papers by looking at the results without looking at the proofs first. It is said that more complicated proofs are overrated - proving a stronger theorem with a trivial proof might get a rejection.
ReplyDeleteFWIW, when I review I usually read only as far as the precise statement of the main result and then think about how I would prove the result before reading any further. It doesn't help the paper's chances if I can at least sketch the proof in 30 minutes or less. (I quit much sooner than this if I really have no clue how to proceed.)
ReplyDeleteI figure that, if I can answer the question in the 30 minutes, then anyone who seriously needs the result will be able to do so relatively quickly. This may or may not be the right thing to do, but the two stage review process suggested in this post would still let me do it.
On the other hand, I would be perfectly happy accepting a paper that had a truly creative main result with a simply discoverable proof, but that the main result gave simple proofs of many, even known, results. (Think Szekely's "Crossing Numbers and Hard Erdos Problems in Discrete Geometry" in which he didn't even have to prove the main result (the Crossing Lemma).)
I think that this idea is backwards. It is rare in research that you find a theorem which is stated in just the form that you need it, and you can use it an black-box way. It is much more common that you need a version of a result which is slightly modified/extended/generalized, and then you need to understand the proof. In a real sense, there is a "cloud" of related results that are clustered together in idea-space, which cannot be easily generalized into a single master theorem. If you know the proof you own the whole cloud.
ReplyDeleteAs a general technique I agree with Pat, however it is important to remember that sometimes the contribution lies in asking the right question. For example linear programming was easily solvable (in fact as it turned out we already had existing polynomial time solutions) once the question was properly phrased in terms of digits of precision required in the solution.
ReplyDeleteSo the first question one should ask is: had I ran into this problem would I have phrased it this way?
A second scenario is: the question is easily posable, relatively easy to answer, and quite relevant, yet for some reason people never asked it, leaving a hole in an important part of the space. This doesn't happen often of course. Personally, I have exactly one paper in my entire academic life like this. To the reviewer's credit it was accepted with reviews citing precisely the reasons above: important question, natural, easy to answer, yet surprisingly not asked in over 25 years of research on the subject.
tl;dr there are many reasons why a result is worth publishing---including proof technique and/or sophistication. Yet presently conferences seem to generally be overly focused on these last two to the detriment of all other good reasons for publication.
I guess this is yet another attempt at linearly ordering a partial order.
ReplyDelete(This is Bill Gasarch)
ReplyDeleteSome papers say `Although the theorem is not new, the techniques used to prove it are interesting in their own right''.
I wonder for how many of them this is really true.
More honest would be
``Although the theorem proved is neither new nor interesting the proof techniques used may or may not be useful to prove other theorems which may or many not be
of interest.''
What about Erdos' THE Book in this context?
ReplyDelete"Although the theorem proved is not interesting and the proof is so horribly complicated that is unlikely to ever be of use, nonetheless the reviewers felt the need to pass on this pointless exercise in baroqueness to unsuspecting conference attendees".
ReplyDeleteIn my opinion every STOC/FOCS has a dozen papers like this and often even hold them in high regard.
What about a 'The Journal of Theorems' which will be judging papers exactly following your criteria?
ReplyDelete