tag:blogger.com,1999:blog-3722233.post112144270908323055..comments2021-09-28T10:13:47.638-05:00Comments on Computational Complexity: Do Only Simple Theorems Have Simple Proofs?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-1121678229480918152005-07-18T04:17:00.000-05:002005-07-18T04:17:00.000-05:00Lance, Please comment also on the value STOC/FOCS ...Lance, <BR/>Please 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.<BR/>Has there been a case when these conferences accepted such papers?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121654296353089762005-07-17T21:38:00.000-05:002005-07-17T21:38:00.000-05:00-- ``Simple proofs get rejected because So-and-so'...-- ``Simple proofs get rejected because So-and-so's paper was turned down'' does not add much to the debate.<BR/><BR/>Sure, 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121648260029792762005-07-17T19:57:00.000-05:002005-07-17T19:57:00.000-05:00From my viewpoint (coming from crypto...) the most...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121516573415584972005-07-16T07:22:00.000-05:002005-07-16T07:22:00.000-05:00When I'm a PC member, if a paper has a complex pr...When 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.<BR/><BR/>Of 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121488426013639002005-07-15T23:33:00.000-05:002005-07-15T23:33:00.000-05:00Also, the undecidability of Halting problem seems ...Also, 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.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121477344804383712005-07-15T20:29:00.000-05:002005-07-15T20:29:00.000-05:00I think the distinction is between an argument lik...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...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121475636099413692005-07-15T20:00:00.000-05:002005-07-15T20:00:00.000-05:00The ancient greek mathematicians had proofs that a...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?<BR/><BR/>The moral of the story? If you want to go for the long-term, go for the simple proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121471420832959712005-07-15T18:50:00.000-05:002005-07-15T18:50:00.000-05:00STOC/FOCS papers are not ends in themselves.Ah, bu...<I>STOC/FOCS papers are not ends in themselves.</I><BR/><BR/>Ah, but to many of us still trying to establish our careers, they are.<BR/><BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121461929860006972005-07-15T16:12:00.000-05:002005-07-15T16:12:00.000-05:00Jeff seems to suggest that there is a distinction ...Jeff seems to suggest that <BR/>there is a distinction between<BR/>"simple" and "easy" proofs and that<BR/>can be consistently recognized. <BR/>Is it so clear?<BR/>What about an easy proof that <BR/>everyone has missed but the theorem<BR/>is really good. Sometimes <BR/>stating a theorem in a right way<BR/>or generalizing it enough makes it<BR/>much more useful and interesting.<BR/>The proof might be implicit in<BR/>a special case. Is the proof then<BR/>easy or simple? There are no<BR/>clear cut answers to these questions.<BR/>The PC tries to figure out all<BR/>this messy stuff and makes a<BR/>decision. Unless there are systematic inconsistencies or<BR/>biases that can be seen via <BR/>some kind of reasonable data<BR/>analysis, there is no point in <BR/>quibbling over a few decisions<BR/>here and there. STOC/FOCS papers<BR/>are not ends in themselves. Too<BR/>much navel gazing can be harmful!<BR/>Go prove a nice theorem (and give<BR/>a simple proof if you can).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121460855139636092005-07-15T15:54:00.000-05:002005-07-15T15:54:00.000-05:00It seems, then, that the following is the best str...It seems, then, that the following is the best strategy:<BR/><BR/><B>1.</B> Submit a complicated proof of your result. Assuming the result is interesting, it will be accepted because it looks nontrivial.<BR/><BR/><B>2.</B> 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121460181150517082005-07-15T15:43:00.000-05:002005-07-15T15:43:00.000-05:00There has been alot of comments inthis weblog abou...There has been alot of comments in<BR/>this weblog about what STOC and FOCS<BR/>do or have a reputation for doing.<BR/>Has anyone done a systematic study of this<BR/>(I doubt it.) I would be very curious to<BR/>have some of the factual issues understood<BR/>before we complain. Annecdotal evidence<BR/>an only take you so far.<BR/>Questions:<BR/><BR/>Do they REALLY have a bias against Simple<BR/>proofs?<BR/><BR/>Have things REALLY gotten better?<BR/><BR/>How much does being in a HOT FIELD matter?<BR/><BR/>I don't expect answers to these questions,<BR/>but realize that the response<BR/><BR/>``Simple proofs get rejected because<BR/>So-and-so's paper was turned down''<BR/><BR/>does not add much to the debate.<BR/>Nor does<BR/><BR/>``If So-and-so was submitted now it<BR/>would be turned down.''<BR/><BR/>How to study the issue?<BR/>Getting a list of simple results that<BR/>were ACCEPTED would be easy, though<BR/>time consuming (hmmm- who defines easy?)<BR/>Getting a list of simple and important<BR/>results that were turned down would be<BR/>much harder.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121460088308589022005-07-15T15:41:00.000-05:002005-07-15T15:41:00.000-05:00What about hiring committees? Do you think they a...What about hiring committees? Do you think they also tend to prefer complicated proofs?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121456241605750262005-07-15T14:37:00.000-05:002005-07-15T14:37:00.000-05:00"The program committee has to decide whether the r..."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."<BR/><BR/>Not this tired excuse again. There is a huge difference between an SIMPLE proof and an EASY proof (unless P=NP). Results that appear easy in retrospect (like Savitch's theorem) are not necessarily easy to discover or communicate; it takes a lot of effort to make things look simple.<BR/><BR/>Unfortunately, STOC/FOCS has a reputation for rejecting simple results, regardless of their actual significance.Jeff Ericksonhttps://www.blogger.com/profile/08256919779078679044noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1121446073557589032005-07-15T11:47:00.000-05:002005-07-15T11:47:00.000-05:00Probably even a 1-paragraph proof of the Unique Ga...Probably even a 1-paragraph proof of the Unique Games Conjecture would be welcome in STOC/FOCS.<BR/><BR/><BR/>Speaking 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.Anonymousnoreply@blogger.com