tag:blogger.com,1999:blog-3722233.post4828575039148806480..comments2021-07-28T08:28:37.990-05:00Comments on Computational Complexity: What is a breakthrough? Lets have an intelligent discussion!!!!!!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger24125tag:blogger.com,1999:blog-3722233.post-58252257324215223462011-01-09T07:05:46.906-06:002011-01-09T07:05:46.906-06:00From what I understand, there is real hope that th...From what I understand, there is real hope that the new technique in the recent paper on TSP can be extended to the general metric, i.e. break the 3/2 bound for metric TSP.<br /><br />Aside from that, this new paper has some very interesting results. For example, the new properties proved for the structure of near-minimum cuts is rather interesting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8445963169304469092011-01-07T14:49:59.808-06:002011-01-07T14:49:59.808-06:00To those who sneer at the value of epsilon, I wond...<i>To those who sneer at the value of epsilon, I wonder whether they would be impressed by 4/3 as opposed to 3/2.</i><br /><br />I think everyone would be more impressed by 4/3 than 3/2 - 10^{-13}, which is the approximation ratio claimed by this paper. <br /><br />That said, trying to analyze "what is a breakthrough" seems to be nothing but harmful. It's strange (but admittedly amusing) how some have managed to turn TCS into a spectator sport.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15412812796669365632011-01-06T22:19:26.768-06:002011-01-06T22:19:26.768-06:00The definition of "breakthrough" aside, ...The definition of "breakthrough" aside, I think there are a few good things to be said about the new TSP algorithm which I have not seen in the debate so far.<br /><br />First, I don't think a comparison with Euclidean TSP (which came up in the other thread) is very accurate. The euclidean case has a substantially different flavor. I believe the new paper should be seen as a viable proposal of a technique to attack the general metric case, rather than a solution for a particular special case. It seems that the reason it's currently for the unweighted case might be just a technicality, or perhaps not - that remains to be seen.<br /><br />To those who sneer at the value of epsilon, I wonder whether they would be impressed by 4/3 as opposed to 3/2. If you hate approximation algorithms in the first place, probably not. But the question is not only whether 3/2 is optimal, but also whether we can get any better understanding of the problem.<br /><br />Apart from the criteria of greatness mentioned above, I think there is also value in bringing together seemingly unrelated techniques, which is what the new paper does (just like the other exciting papers mentioned above). The particular techniques (Benczur's representation of near-minimum cuts and correlation properties of random spanning trees) are going to be interesting for some more than for others, but the fact the techniques came from different communities is often a sign of something interesting happening. <br /><br />Which of the papers above should be called a breakthrough will be more clear in a few years, I think.Jannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84434978318069909392011-01-05T19:52:42.519-06:002011-01-05T19:52:42.519-06:00Erdos Distance Problem: YES, I mispoke (mistyped?)...Erdos Distance Problem: YES, I mispoke (mistyped?) - I should have<br />said solved within-a-log-factor<br />or something of that sort.<br /><br />Still very impressive.<br />I've also seen it stated as<br />showing that g(n) \ge n^{2-ep}<br />for all ep>0. So THAT version has been solved.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61342633812226645472011-01-05T17:20:13.855-06:002011-01-05T17:20:13.855-06:00Above you said that Erdos Distance really was solv...Above you said that Erdos Distance really was solved. Isn't it currently at O(n/sqrt(log n))≥g(n)≥Ω(n/log n)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53953748216104363652011-01-05T10:25:40.103-06:002011-01-05T10:25:40.103-06:00GASARCH proposes: What is a breakthrough? Lets hav...GASARCH proposes: <i>What is a breakthrough? Lets have an intelligent discussion.</i><br /><br />Anonymous responds: <i>You became like people magazine. i wonder how much lower this blog can go.</i><br /><br />Upon reading a good article in CS/CT/QIT, for me (and many people) it is routine practice to check for a Fortnow/ GASARCH/ Lipton/ Regan/ Tau/ Kalai/ Aaronson/ Bacon/ Gowers (etc.) commentary upon it ... and very often we are glad when we find that a commentary exists (<a href="http://blog.computationalcomplexity.org/2007/09/social-process-and-proofs-of-theorems.html" rel="nofollow">here is a GASARCH commentary from 2007, for example</a>).<br /><br />That the CT blogosphere is the last word is, of course, expected by nobody:<br /><br />------------<br />Tell all the Truth but tell it slant --<br />Success in Circuit lies<br />Too bright for our infirm Delight<br />The Truth's superb surprise<br /> — <i>Dickinson</i><br />------------<br /><br />Whatever heuristic the CT bloggers are using to evaluate good papers/ good mathematics/ interesting ideas, it seems (to me) that this heuristic is working reasonably well in practice.<br /><br />Give us more, please!John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75878523471212746512011-01-04T23:35:31.573-06:002011-01-04T23:35:31.573-06:00you became like people magazine. i wonder how muc...you became like people magazine. i wonder how much lower this blog can goAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57699359709069011282011-01-04T11:25:36.116-06:002011-01-04T11:25:36.116-06:00Anonymous proposes: ... minor breakthroughs ... ma...Anonymous proposes: <i>... minor breakthroughs ... major breakthroughs ... monumental breakthroughs ...</i><br /><br />Duh ... don't we need yet another term to describe "breakthroughs" that settle questions and provide capabilities whose very existence, even, had not previously been foreseen? Shannon's <i>Theory of Communication</i>, for example.<br /><br />Maybe we should call them ... "epochal" breakthroughs? :)<br /><br />This hair-splitting reminds me irresistibly of the <a href="http://dc-cdn.virtacore.com/2010/11/f7a07658a3644ae4a932c468bd7f2a64.jpg" rel="nofollow">US Homeland Security's Advisory System</a> ... hmmm ... how well did *that* work out?<br /><br />It seems to me that Terry Tao's way of thinking works better: <br /><br />----------------<br />The concept of mathematical quality is a high-dimensional one and lacks an obvious canonical total ordering ... [Yet nonetheless] there does however seem to be some undeﬁnable sense that a certain piece of mathematics is “on to something”, that it is a piece of a larger puzzle waiting to be explored further.<br />----------------<br /><br />Very plausibly, in 2010 there <i>were</i> some Tao-style "on to something" breakthroughs ... yet history suggests that we will come to an appreciation of them only slowly.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82269229119573705892011-01-04T08:05:31.087-06:002011-01-04T08:05:31.087-06:00I think that a minor breakthrough is one in which ...I think that a minor breakthrough is one in which a hard, important problem that has been open for a "short" time ("short" relative to our time scales in CS, obviously), say approximately 5 years, that has resisted prior attempts, is solved. <br />E.g., Arora, Barak, Steurer.<br /><br />A major breakthrough is one that solves a hard, important problem that has been open for longer, say on the scale of decades. E.g., Williams' result.<br /><br />And a monumental breakthough (call it a landmark, epochal breakthrough, whatever) should be one that settles a central open problem of the field, e.g., P neq NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55965706533229806102011-01-03T22:22:24.871-06:002011-01-03T22:22:24.871-06:00Most theoretical computer scientists agree that ap...<i>Most theoretical computer scientists agree that approximation algorithms are important. There are many reasons for this, that are beyond the scope of this post.</i><br /><br />Most theoretical computer scientists agree that today's trends are obviously interesting and important, but they often look down on yesterday's trends (e.g., PRAMs). The real question is what tomorrow's theorists will think of today's trends, and that can't be settled by conducting a poll today.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56372476882334850862011-01-03T20:45:21.809-06:002011-01-03T20:45:21.809-06:00I propose the formation of a new discipline, "...I propose the formation of a new discipline, "breakthrough studies". <br /><br />One of the fundamental objectives in breakthrough studies is to come up with a rigorous and objective notion of what constitutes a breakthrough. This might seem to be a very difficult task, but we have an important clue - the discovery of an exact notion of breakthrough would itself obviously be a breakthrough, therefore the concept must apply to itself in some sense. <br /><br />If we adhere closely to this initial insight, I am confident that the great minds of the blogosphere, working together, can set the new field of breakthrough studies in motion, towards the discovery of many more breakthrough insights into the nature of breakthrough insights.Mitchellhttps://www.blogger.com/profile/10768655514143252049noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17072195885604096992011-01-03T19:58:48.034-06:002011-01-03T19:58:48.034-06:00"You really should reserve scores of 10 for r..."You really should reserve scores of 10 for real breakthroughs. Even a correct proof that P!=NP would not deserve all 10s since the question of practical relevance is whether _randomized_ algorithms can solve NPC problems, and hence a progress rating of about 9.5 would be appropriate..."<br /><br />If you will, please imagine the ratings as being on a scale of 1 to 1,000,000. Then a proof of P!=NP would be a 999,000 and every result from the last ten years would lie from 1 to 10. Amazingly (!), this lets us use the 1-10 rating scale in a sane way, exactly as Gasarch was already doing. ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78195194964694441662011-01-03T19:04:22.711-06:002011-01-03T19:04:22.711-06:00To address the topic more seriously, then, I don&#...To address the topic more seriously, then, I don't think that "breakthroughs" are a subset of "big important results". I think that to be a breakthrough, one must break through a barrier people previously thought was preventing progress. But the step through the barrier might be small, and the place one gets to from that step might not be so important. So in this sense I think Ryan's circuit complexity result is a breakthrough, and definitely deserves a place in any list of top complexity results from the year, despite taking a small step to a result that is not per se important.<br /><br />The TSP claim seems less of a breakthrough to me. We already knew special cases of TSP that could be approximated better than 3/2, and this is just another special case. Also I don't think there was strong belief in a barrier at 3/2; wasn't there a STOC/FOCS paper a few years back that strongly suggested that 4/3 should be possible?D. Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77307286278553145542011-01-03T17:21:39.782-06:002011-01-03T17:21:39.782-06:00The first half of the post- the
criteria, is an at...The first half of the post- the<br />criteria, is an attempt at beginning an intelligent discussion of the issue<br /><br />The second half- actually rating the recent alleged breakthroughs,<br />is of course (as I said in the post)<br />very silly. I did it just to se<br />what would happen.<br /><br />YES, the ratings are in general way to high with one exception.<br />Erdos-Distance problem really was solved,<br />so that gets a very high rating for<br />progress on the problem<br />.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79303855565880513382011-01-03T16:33:16.370-06:002011-01-03T16:33:16.370-06:00You really should reserve scores of 10 for real br...You really should reserve scores of 10 for real breakthroughs. Even a correct proof that P!=NP would not deserve all 10s since the question of practical relevance is whether _randomized_ algorithms can solve NPC problems, and hence a progress rating of about 9.5 would be appropriate for a proof of P!=NP. In this light your rating of "IMPORTANT: 10 and PROGRESS: 8" for the CB result is ridiculous. Either the question being addressed by CB is P!=NP, in which case the importance of 10 is appropriate but the progress score should be at most 3, or else the problem in question is some stepping stone problem of much lesser importance.<br /><br />-WarrenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63504893545637778802011-01-03T16:17:53.875-06:002011-01-03T16:17:53.875-06:00Most theoretical computer scientists agree that ap...<i>Most theoretical computer scientists agree that approximation algorithms are important. </i><br /><br />Several well known theoreticians have started to complain about the lack of applicability of approximation algorithms. The agreement might not be as universal as you think.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40472283340931576982011-01-03T15:45:46.372-06:002011-01-03T15:45:46.372-06:00First anonymous: This is a blog about theoretical ...First anonymous: This is a blog about theoretical computer science. Most theoretical computer scientists agree that approximation algorithms are important. There are many reasons for this, that are beyond the scope of this post. Therefore, your criteria of "important only if used in practice today" does not hold water in this crowd, and is unlikely to be taken seriously.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19633733831202795532011-01-03T15:27:33.907-06:002011-01-03T15:27:33.907-06:00I agree with Eppstein. These multiple exclamation...I agree with Eppstein. These multiple exclamation blog posts are really cringe-inducing and embarrassing to the whole community, sadly.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12537960698109238512011-01-03T15:16:25.204-06:002011-01-03T15:16:25.204-06:00For better or for worse, the current definition of...For better or for worse, the current definition of "breakthrough" in the TCS community seems to be "was discussed in a blog post".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8767796122138611272011-01-03T14:31:05.161-06:002011-01-03T14:31:05.161-06:00Progress score for CLB sounds too high. It is rema...Progress score for CLB sounds too high. It is remarkable that after so long something new has been proven there, but in an absolute scale the movement is rather minor. I also agree with first anon that importance for AUG is overstated. Say, we are unlikely to be teaching that paper fifteen years from now in a grad course. Consider in contrast the original TSP paper, or the PGP paper, or the smoothed analysis paper. I'd be willing to bet those will still be grad course material in 2025.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25764978839447326952011-01-03T14:20:43.584-06:002011-01-03T14:20:43.584-06:00An "intelligent discussion" in which we ...An "intelligent discussion" in which we supply numerical ratings in the range of 7-10 for quantities such as "importance" without specification of importance to whom? Where even a somewhat-isolated pure mathematics problem gets a score of 7 and a proof of a complexity separation that everyone thought obviously true gets a score of 10? Would a proof of P=NP be 11 on this scale, and even if so why would it be considered only 57% more important than the arithmetic progression problem? What is the justification (in utility theory, say) for combining these scores by adding them? And for that matter, why is there nothing in these scores for mathematical beauty?<br /><br />I'm struggling to see the "intelligent" part of the discussion here. It just looks like cheerleading and post-facto justification for the conclusions you already want to believe (we are achieving great things!) to me. Don't get me wrong; I think cheerleading is a fine thing to do. If I didn't think that I wouldn't have recently made a top-ten-of-the-year post myself. I just think one should be more honest about it rather than trying to pretend one is doing science by measuring things numerically.D. Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12774811960748934622011-01-03T13:31:39.212-06:002011-01-03T13:31:39.212-06:00Andy D- Thanks, I have fixed it.Andy D- Thanks, I have fixed it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81860791373892237662011-01-03T13:03:39.256-06:002011-01-03T13:03:39.256-06:00On item 6, you forgot Shang-Hua Teng on your autho...On item 6, you forgot Shang-Hua Teng on your author list. Also, 'Christano' should be 'Christiano'.Andy Dnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64869943284874884452011-01-03T12:32:20.165-06:002011-01-03T12:32:20.165-06:00I would give UGC problem a 5 in importance. Approx...I would give UGC problem a 5 in importance. Approximation algorithms are not used anywhere in practice, which diminishes the importance of a conjecture about the hardness of approximation of various problems.Anonymousnoreply@blogger.com