tag:blogger.com,1999:blog-3722233.post9003988703313356477..comments2022-01-27T09:59:22.665-06:00Comments on Computational Complexity: The Theorems ConferenceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-61808582856965974942015-09-20T19:17:00.832-05:002015-09-20T19:17:00.832-05:00What about a 'The Journal of Theorems' whi...What about a 'The Journal of Theorems' which will be judging papers exactly following your criteria?Shehabhttps://www.blogger.com/profile/14005206657539890819noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50701091992717354622015-09-18T15:42:47.370-05:002015-09-18T15:42:47.370-05:00"Although the theorem proved is not interesti..."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".<br /><br />In my opinion every STOC/FOCS has a dozen papers like this and often even hold them in high regard.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63624940843032790822015-09-18T15:10:18.585-05:002015-09-18T15:10:18.585-05:00What about Erdos' THE Book in this context?What about Erdos' THE Book in this context?stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83897284781736792042015-09-18T10:35:55.586-05:002015-09-18T10:35:55.586-05:00(This is Bill Gasarch)
Some papers say `Although t...(This is Bill Gasarch)<br />Some papers say `Although the theorem is not new, the techniques used to prove it are interesting in their own right''.<br />I wonder for how many of them this is really true.<br />More honest would be<br /><br />``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<br />of interest.''<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22232299406524412802015-09-17T16:37:57.057-05:002015-09-17T16:37:57.057-05:00I guess this is yet another attempt at linearly or...I guess this is yet another attempt at linearly ordering a partial order.Chandrahttps://www.blogger.com/profile/00057069075567569157noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83919315634711536172015-09-17T15:04:19.467-05:002015-09-17T15:04:19.467-05:00As a general technique I agree with Pat, however i...As 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.<br /><br />So the first question one should ask is: had I ran into this problem would I have phrased it this way? <br /><br />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.<br /><br />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.Alex Lopez-Ortizhttps://www.cs.uwaterloo.ca/~alopez-onoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55956173435395369902015-09-17T14:10:30.528-05:002015-09-17T14:10:30.528-05:00I think that this idea is backwards. It is rare in...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.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48726758839507125792015-09-17T12:43:32.641-05:002015-09-17T12:43:32.641-05:00FWIW, when I review I usually read only as far as ...FWIW, 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.)<br /><br />I 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.<br /><br />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).) Anonymoushttps://www.blogger.com/profile/06328185728688465505noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46872792966855190822015-09-17T09:48:29.077-05:002015-09-17T09:48:29.077-05:00I really like this suggestion, but imo all (or at ...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.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86693372176351860172015-09-17T07:16:22.682-05:002015-09-17T07:16:22.682-05:00p.s. We recently ran into this problem ourselves. ...p.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.<br /><br />Sadly, 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.Alex Lopez-Ortizhttps://www.cs.uwaterloo.ca/~alopez-onoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6505749328741287962015-09-17T07:08:42.516-05:002015-09-17T07:08:42.516-05:00Ironically Pascal and Anonymous confirm the need f...Ironically Pascal and Anonymous confirm the need for this conference. They completely forget that the <i>statement of the theorem</i> itself adds to the toolkit. For example, Hopcroft-Karp perfect matching algorithm is used as a blackbox in many sophisticated follow up results.Alex Lopez-Ortizhttps://www.cs.uwaterloo.ca/~alopez-onoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32276688747828868672015-09-17T05:16:57.899-05:002015-09-17T05:16:57.899-05:00Agreeing with Pascal. Particularly in my field (al...Agreeing 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, ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51740089207508456172015-09-17T03:17:50.731-05:002015-09-17T03:17:50.731-05:00Why insist on a culture shift in the first place? ...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.Pascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.com