tag:blogger.com,1999:blog-3722233.post8196403551360103752..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: What is a Breakthrough?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-3722233.post-52592646969249506352011-12-29T17:49:38.381-06:002011-12-29T17:49:38.381-06:00For practical means, I would consider a theorem a ...For practical means, I would consider a theorem a break-through if it is stated in high venues of publication by at least two reputable experts in the area and two reputable authors not working in the area with no conflict of interests, independently, and before the result becomes known that solving the problem will be a break-through and it becomes common knowledge by people working in the area that this would be considered a break-through by these people and the problem remains as open at least a few years (say 5) after that.<br /><br />Some time will be needed to pass before evaluating the importance of the break-through.<br /><br />Assuming that natural proofs is a recognized barrier for the separation proven by Ryan Williams (and probably even without it) I would consider his result a break-through. So far I haven't seen enough evidence supporting Andrew Stothers and Virginia Vassilevska Williams's results as such according to my criteria.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1904473244051934782011-12-10T16:07:43.581-06:002011-12-10T16:07:43.581-06:00Dear Gil, without endorsing the notion that the fo...Dear Gil, without endorsing the notion that the following data should be taken seriously: (a) during the years 1991-5 the work "breakthrough" appeared in 105 MathSciNet reviews out of 294,545, for an incidence of 1/2805; (b) during the years 2006-10 the work "breakthrough" appeared in 241 reviews out of 465,212, for an incidence of 1/1903.<br /><br />In other words, the number of MathSciNet reviews doubles (very roughly) every 23 years, and the fraction of reviews that mention "breakthroughs" doubles (very roughly) every every 27 years. <br /><br />In the words of Mark Twain: "Therefore, any calm person, who is not blind or idiotic" can calculate that in the year 2300 MathSciNet will index six hundred million new mathematics articles (equivalently, one new article every 20 milliseconds) and <i>all</i> of these reviews will be "breakthroughs". <br /><br />Thus will mathematical utopia become a reality (or will it? … a topic worthy of Neil Stephenson's <a href="http://www.worldpolicy.org/journal/fall2011/innovation-starvation" rel="nofollow"><i>Heiroglyph Project</i></a>). <br /><br />Just as Lance says: it's "A Great Time to be a Computer Scientist." :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9064156931721839172011-12-10T15:50:26.802-06:002011-12-10T15:50:26.802-06:00I skimmed through some reviews in recent years, it...I skimmed through some reviews in recent years, it seemed that a lot of them are actually from fields like statistics, medicine, computer science, etc...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26494574964577699832011-12-10T13:57:22.575-06:002011-12-10T13:57:22.575-06:00Dear John, i just wanted to see if the increase of...Dear John, i just wanted to see if the increase of using the term breakthrough reflects the increase in the total number of reviews. namely if the 1:3000 ratio is more or less the same over the last decades. I cannot say much on the general question of "what is a breakthrough". For a single mathematician there is this experience that you hit your head against the wall again and again and then someday you can prove something (and the proof remains correct after you check it). And this is a clear individually breakthrough sensation.Gil Kalaihttp://gilkalai.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11343120050511867512011-12-09T12:06:03.785-06:002011-12-09T12:06:03.785-06:00Gil, the total MathSciNet database has (apparently...Gil, the total MathSciNet database has (apparently) 2723609 entries, of which 874 reviewer texts include the word "breakthrough". Thus (very roughly) about one review in 3000 uses the term "breakthrough". <br /><br />My own (informal) opinion is that "breakthrough" is *not* a devalued term, that is, the mathematics community really is producing breakthrough results at an accelerating pace, precisely as one would hope and expect from an increasing population of mathematicians drawing inspiration from an increasing body of literature.<br /><br />On the other hand, as one might expect, some articles suggest that having more mathematical breakthroughs may not be an unalloyed good. For example, Natali Hritonenko and Yuri Yatsenko argue in "Technological innovations, economic renovation, and anticipation effects" (MR2739540) that foreknowledge of impending breakthroughs can act to <i>inhibit</i> rational economic investment.<br /><br />Hmmmm … does the Hritonenko-Yatsenko mechanism create a mathematical tragedy of the commons? If mathematicians were to cease advertising "breakthroughs" — and scientists, engineers and physicians followed suit — would the global recession swiftly end, as investors regained their confidence in existing business models? ;)<br /><br />Obviously the relation between breakthroughs, enterprise, and investment is more subtle than *that*!John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70567738524179010052011-12-09T09:50:19.654-06:002011-12-09T09:50:19.654-06:00The MR statistics is very interesting, John. Do yo...The MR statistics is very interesting, John. Do you know how many papers were reviewed altogether in these years?Gil Kalaihttp://gilkalai.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48432374288754524762011-12-08T06:22:24.926-06:002011-12-08T06:22:24.926-06:00Upon searching the MathSciNet review texts for the...Upon searching the MathSciNet review texts for the word "breakthrough", we find an early usage in Apostol's review of Rankin's 1960 article "Sets of integers containing not more than a given number of terms in arithmetical progression" (MR0142526):<br /><br />---------------------<br /><i>Apostol:</i> The author [Rankine] makes a major breakthrough by obtaining an extension of Behrend's result for sets of type [1,n]."<br />---------------------<br /><br />Interestingly, Rankine-type results for arithmetical progressions are presently the main topic of <i>Gödel's Lost Letter and P=NP</i> ("Theorems are Forever"); so evidently Apostol was correct to regard Rankine's results as a "breakthrough."<br /><br />Since 1960, there has been a striking exponentiation in the number of mathematical breakthroughs (as evaluated by MathSciNet reviewers in the "review text" field):<br /><br />---------------------<br /> YEAR RANGE<br />(first-last) # breathroughs<br />1951-55: 000 breakthroughs<br />1956-60: 003<br />1961-65: 007<br />1966-70: 007<br />1971-75: 009<br />1976-80: 029<br />1981-85: 055<br />1986-90: 071<br />1991-95: 105<br />1996-00: 160<br />2001-05: 182<br />2006-10: 241 breakthroughs<br />---------------------<br /><br />Does this reflect a hundred-fold increase in the number of Rankine-class mathematical breakthroughs? Are we really seeing (roughly) one mathematical breakthrough per week nowadays? It seems to me that the answer is simply "yes". <br /><br />In which case, a natural follow-on question is associated to Steve Denning’s economic analysis in his recent much-discussed <i>Forbes</i> essay titled “Why We Are In Political Gridlock: The Private Sector Is Dying” (key numbers <a href="http://blogs-images.forbes.com/stevedenning/files/2011/11/Shift-Index-ROA1.jpg" rel="nofollow">are shown in this graphic</a>).<br /><br />That natural follow-on question is: Why is the 21st century's 100X increase in mathematical breakthroughs not catalyzing at least a modest increase in enterprise and investment opportunities?<br /><br />It is clear that the 21st century is awash in (1) people, (2) cash, and (3) breakthroughs. So why is the 21st century not awash in productive enterprises? What is missing?<br /><br />To me, these natural follow-on questions are even more interesting than "What is a breakthrough?", and the answers — if we can conceive them — will largely determine whether the 21st century is (reasonably) utopian versus (horrendously) dystopian.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3755681787507507162011-12-08T03:09:53.211-06:002011-12-08T03:09:53.211-06:00This list doesn't look like the answer to &quo...This list doesn't look like the answer to "What is a breakthrough?", but rather the answer to "What is publishable?"JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65869928692748941432011-12-08T01:47:01.927-06:002011-12-08T01:47:01.927-06:00"A blogger insisting something is a breakthro..."A blogger insisting something is a breakthrough doesn't make it so"<br /><br />Stop such lame arguments.<br /><br />These blogs are read by enough people in the community, they are not just rants by some random blogger.<br /><br />It's like Barack Obama twitting nonsense on the internet then claiming it's a joke because his twitter is personal".<br /><br />If this is "just a blog" then have some security settings on and limit access to your close friends only, that way you avoid any criticism whatsoever.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39113189034325147622011-12-07T18:37:48.876-06:002011-12-07T18:37:48.876-06:00All this talk of "breakthroughs" and the...All this talk of "breakthroughs" and the constant stream of horrible comments on these blogs is depressing. A blogger insisting something is a breakthrough doesn't make it so, and an anonymous troll insisting something *isn't* a breakthrough also doesn't make it so. Who cares? Everyone, if you want algorithms/complexity to stay "alive", please, stop trying to kill it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16363081233597752242011-12-07T17:20:28.000-06:002011-12-07T17:20:28.000-06:00The only way I can approach this is based on speci...The only way I can approach this is based on specific examples. Here's one that fits: It concerns formula size lower bounds for explicit functions over the De Morgan basis. In the 1960's there were several methods by Subbotovskaya, Neciporuk, Krapchenko that obtained such lower bounds of n^{3/2}, n^2/log n, and n^2 respectively, even though counting arguments said that "most" functions require exponential size. Many people tried to improve this without success and the limit in the exponent always seemed to be 2.<br /><br />In the late 1980's Andreev showed that a combination of Subbotovskaya's technique and counting arguments would yield a roughly n^{2.5} lower bound. It was very clear that from any such argument, n^3 was an upper limit of the technique, though it wasn't clear that it could be reached. A short while later, this is roughly what Hastad achieved.<br /><br />Andreev's argument was a breakthrough in some sense (though it mostly combined two old techniques in a novel way) but it would be harder to argue that Hastad's paper, which introduced some much more sophisticated machinery, was also a breakthrough.<br /><br />The point is that the breakthrough paper changed the mind-set of the people working in the area. It "broke through" a conventional idea. Not all breakthroughs need to be important. They just need to change experts' long-held thinking about a problem or area. Moreover, a paper can be fundamental and important even if it is not a breakthrough.Paul Beamehttp://www.cs.washington.edu/homes/beame/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74929944018130995422011-12-07T16:51:45.032-06:002011-12-07T16:51:45.032-06:00Why are you picking such fight again? This is way ...Why are you picking such fight again? This is way over the top.<br /><br />If someone write that this is a breakthrough in a grant proposal and/or their CVs then I doubt too many people would actually bother popping out moaning.<br /><br />If you want to do PR for complexity then start with something like PCP or AKS. I really don't see what is the transcendental value in the Williams result?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73001466792968339712011-12-07T16:20:42.464-06:002011-12-07T16:20:42.464-06:00For two (related) breakthroughs, I'd nominate:...For two (related) breakthroughs, I'd nominate: <br />Balanced Allocations<br /> http://dl.acm.or/citation.cfm?id=195058.195412<br /><br />The "idea" had been floating out there (in a paper by Karp, Luby, and Meyer auf der Heide), but this paper put the "power of two choices" in such a simple and natural framework (and provided a useful technique for power of two choice results).<br /><br />Following in that line, I'd also suggest as a breakthough:<br />How asymmetry helps load balancing<br /> http://dl.acm.org/citation.cfm?id=792546 <br />Berthold's result just smacks you over the head (how can asymmetry help, there was a lower bound in the Balanced Allocations paper?), and then, when you think about it, becomes transparently obvious and you wonder how you didn't see it before.<br /><br />Of course, I like balls and bins papers.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63518843923579121702011-12-07T16:05:38.915-06:002011-12-07T16:05:38.915-06:00Such discussion is absolutely pointless.
It's...Such discussion is absolutely pointless.<br /><br />It's like layout a definition sheet to argue about what is beautiful. These are things for which we are able to make reasonable subjective judgement.<br /><br />In mathematics a true breakthrough genuinely impresses any honest people who actually understand the work.<br /><br />The fact that there is such debate simply means that this result failed to impress most people. This already falsifies the claim about the significance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38733058727192098462011-12-07T15:59:31.148-06:002011-12-07T15:59:31.148-06:00Yet another person whose writings comprise (in GAS...Yet another person whose writings comprise (in GASARCH's words) "an intelligent contribution to this topic [of breakthroughs]" is Elias Zerhouni (former NIH director, architect of the NIH Roadmap, Senior Fellow at the Gates Foundation, US Science Envoy, etc.)<br /><br />Zerhouni's speeches and writings carefully distinguish <i>break-throughs</i> within disciplines from <i>barrier-breaks</i> between disciplines; in Zerhouni's view it is the latter that gives value to the former. <br /><br />--------------<br />"<a href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2657862/" rel="nofollow">We realized that the progress of our discipline</a> was going to be determined precisely by our ability to break barriers between disciplines. ... Let me be explicit. This explosion of scientific knowledge requires us to rethink how we might best advance our understanding. … We simply lack the tools we need to understand these complexities. … If we practice [our profession] in 20 years the way we practice it today, we will have failed. We will have failed the challenge of this century. … A transformation is in the air, regardless of what we do … Our greatest risk is to lack imagination. I have said this before, and I will repeat it — emphatically — now: <i>The greatest risk in science is to stop taking risks.</i>"<br />--------------<br /><br />By Zerhouni's barrier-break criterion, recent advances in our understanding of the asymptotic computational complexity of matrix multiplication surely constitute a break-through in complexity theory, and the value of that break-through in the long run arises mainly from the possibility that someday it will help catalyze barrier-breaks between disciplines. Thus, break-throughs and barrier-breaks alike are hard and alike are vital, and it is useful to distinguish them and value them both.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67711572261626756972011-12-07T13:46:40.961-06:002011-12-07T13:46:40.961-06:00"If someone has a result and does not publish..."If someone has a result and does not publish and publicize it, I would say the result essentially doesn't exist. Galileo's was not the first refracting telescope ever built, but it was built independently, was the first one that after being built was shown and widely disseminated to the public, and that is how it is remembered."<br /><br />If this is yet another attempt to undermine Stothers' result, please note that he did publish his thesis in June 2010, posting it on the internet and making it world accessible. I don't think the comparison with Galileo is apt.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22762314647700964362011-12-07T13:21:37.565-06:002011-12-07T13:21:37.565-06:00Matrix multiplication is something with limitless ...Matrix multiplication is something with limitless applications. That at least influences whether the problem is important: it is very, very important. While from what I understand the constants involved in the new methods are too large to make it practically useful, I that even a small asymptotic improvement of a critical algorithm is important.Lucas Wimanhttps://www.blogger.com/profile/13001386543414706674noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30810639587425208882011-12-07T12:33:59.818-06:002011-12-07T12:33:59.818-06:00The previous commenter is right on: "Some bou...The previous commenter is right on: "Some bounds remain unimproved for a long time because experts see how a very technical computation might lead to an improvement, but this seems very complicated and not really worth the effort."<br /><br />The point is that a breakthrough should satisfy both 1 and 2, not just one or the other.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39757764667180471962011-12-07T10:58:38.278-06:002011-12-07T10:58:38.278-06:00To followup anonymous comment, it was Charles Town...To followup <i>anonymous</i> comment, it was Charles Townes who in his history <i>How the Laser Happened</i> said:<br /><br />--------------------<br />"It is a fine thing to have an idea, and still better to write it up so that other people might use it. It is even better to be the one who not only thinks of something independently, but who makes the invention real in such a way that it is unnecessary and in fact impossible for anybody to invent it again."<br />--------------------<br /><br />In the same vein as Townes, we notice that the semiconductor industry's well-respected International Roadmapping Committee (IRC), in their celebrated <a href="http://www.itrs.net/Links/2010ITRS/IRC-ITRS-MtM-v2%203.pdf" rel="nofollow"><i>More-Than-Moore White Paper</i></a>, use the word "breakthrough" only once (and then only in passing) and the word "theorem" does not appear in the IRC Roadmap at all (although the Roadmap does commonly use the related word "theory", always in the context of practical engineering). The guiding concepts of the IRC Roadmap rather are progress, performance, confidence, investment, and growth---what the IRC calls "The Virtuous Cycle".<br /><br />Is the study of complexity mainly about the informatic dynamics and stability of "virtuous cycles", or is it mainly about "breakthrough theorems"? The answer (obviously) is "both", and so perhaps a good focus of effort would be to couple these two aspects of complexity theory more closely. How can the breakthrough theorems of complexity theory more swiftly evolve into the practical engineering theories that drive virtuous cycles?John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70741104709715347662011-12-07T10:22:14.730-06:002011-12-07T10:22:14.730-06:00If someone has a result and does not publish and p...If someone has a result and does not publish and publicize it, I would say the result essentially doesn't exist. Galileo's was not the first refracting telescope ever built, but it was built independently, was the first one that after being built was shown and widely disseminated to the public, and that is how it is remembered.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62340721384317975412011-12-07T09:56:06.680-06:002011-12-07T09:56:06.680-06:00"The result breaks a long standing barrier&qu..."The result breaks a long standing barrier"<br /><br />How do you define a barrier? Some bounds remain unimproved for a long time because experts see how a very technical computation might lead to an improvement, but this seems very complicated and not really worth the effort. This happens very often. The publication record makes it seem that the problem was stuck for a long time, but I would not call it a conceptual barrier. Before defining what is a breakthrough, it is important to truly understand what is a barrier.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80643820673195235742011-12-07T09:54:01.661-06:002011-12-07T09:54:01.661-06:00I think one difficulty is that it's sometimes ...I think one difficulty is that it's sometimes hard to determine importance right away. We need to wait 5,10, or 20 years and look back and say "was this really important?" <br /><br />If 20 years from now no one has improved the matrix multiplication bound any further, will we still look at the recent result as a breakthrough, or will it just be the last improvement in a long line of slight improvements?Anonymousnoreply@blogger.com