Here are some criteria. The first three are extracted from a comment Gowers made on Scott's Blog. I do not know how many a result has to have to be a breakthrough or even if such a threshold makes sense. Perhaps some sort of weighted sum, but would be hard to define.
- The result breaks a long standing barrier.
- The techniques introduce a fundamentally different method.
- The result is practical (or close to it).
- The problem being discussed is important. This may be a bit circular in that it then depends on What is Important?
- The result has to make substantial progress on the problem. This may depend on What is substantial? That notion may depend on how long the problem has been open.
- There has to be a reason why the problem was thought to be hard. E.g., a proof that a new technique is needed, problem has been open for a long time, people in the field say its hard.
- A paper that STARTS an important field could be a breakthrough. Cook's Theorem and Valiant's PAC learning qualify here.
- A paper that FINISHES a field could be a breakthrough if the field is important. Again this may be a bit circular in that it then depends on What is Important?
- The techniques are new. One might end up debating what is new.
- The techniques can be used on other problems.
- The paper inspires other papers. For this criteria you need to wait a few years. Some papers are not appreciated for a while.
Do you have other criteria, examples, counterexamples, constructive criticism of my criteria, or anything that is an intelligent contribution to this topic? Is so, please post a comment!
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?"
ReplyDeleteIf 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?
"The result breaks a long standing barrier"
ReplyDeleteHow 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.
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.
ReplyDeleteTo followup anonymous comment, it was Charles Townes who in his history How the Laser Happened said:
ReplyDelete--------------------
"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."
--------------------
In the same vein as Townes, we notice that the semiconductor industry's well-respected International Roadmapping Committee (IRC), in their celebrated More-Than-Moore White Paper, 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".
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?
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."
ReplyDeleteThe point is that a breakthrough should satisfy both 1 and 2, not just one or the other.
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.
ReplyDelete"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."
ReplyDeleteIf 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.
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.)
ReplyDeleteZerhouni's speeches and writings carefully distinguish break-throughs within disciplines from barrier-breaks between disciplines; in Zerhouni's view it is the latter that gives value to the former.
--------------
"We realized that the progress of our discipline 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: The greatest risk in science is to stop taking risks."
--------------
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.
Such discussion is absolutely pointless.
ReplyDeleteIt'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.
In mathematics a true breakthrough genuinely impresses any honest people who actually understand the work.
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.
For two (related) breakthroughs, I'd nominate:
ReplyDeleteBalanced Allocations
http://dl.acm.or/citation.cfm?id=195058.195412
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).
Following in that line, I'd also suggest as a breakthough:
How asymmetry helps load balancing
http://dl.acm.org/citation.cfm?id=792546
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.
Of course, I like balls and bins papers.
Why are you picking such fight again? This is way over the top.
ReplyDeleteIf 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.
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?
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.
ReplyDeleteIn 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.
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.
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.
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.
ReplyDelete"A blogger insisting something is a breakthrough doesn't make it so"
ReplyDeleteStop such lame arguments.
These blogs are read by enough people in the community, they are not just rants by some random blogger.
It's like Barack Obama twitting nonsense on the internet then claiming it's a joke because his twitter is personal".
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.
This list doesn't look like the answer to "What is a breakthrough?", but rather the answer to "What is publishable?"
ReplyDeleteUpon 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):
ReplyDelete---------------------
Apostol: The author [Rankine] makes a major breakthrough by obtaining an extension of Behrend's result for sets of type [1,n]."
---------------------
Interestingly, Rankine-type results for arithmetical progressions are presently the main topic of Gödel's Lost Letter and P=NP ("Theorems are Forever"); so evidently Apostol was correct to regard Rankine's results as a "breakthrough."
Since 1960, there has been a striking exponentiation in the number of mathematical breakthroughs (as evaluated by MathSciNet reviewers in the "review text" field):
---------------------
YEAR RANGE
(first-last) # breathroughs
1951-55: 000 breakthroughs
1956-60: 003
1961-65: 007
1966-70: 007
1971-75: 009
1976-80: 029
1981-85: 055
1986-90: 071
1991-95: 105
1996-00: 160
2001-05: 182
2006-10: 241 breakthroughs
---------------------
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".
In which case, a natural follow-on question is associated to Steve Denning’s economic analysis in his recent much-discussed Forbes essay titled “Why We Are In Political Gridlock: The Private Sector Is Dying” (key numbers are shown in this graphic).
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?
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?
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.
The MR statistics is very interesting, John. Do you know how many papers were reviewed altogether in these years?
ReplyDeleteGil, 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".
ReplyDeleteMy 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.
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 inhibit rational economic investment.
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? ;)
Obviously the relation between breakthroughs, enterprise, and investment is more subtle than *that*!
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.
ReplyDeleteI skimmed through some reviews in recent years, it seemed that a lot of them are actually from fields like statistics, medicine, computer science, etc...
ReplyDeleteDear 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.
ReplyDeleteIn 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.
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 all of these reviews will be "breakthroughs".
Thus will mathematical utopia become a reality (or will it? … a topic worthy of Neil Stephenson's Heiroglyph Project).
Just as Lance says: it's "A Great Time to be a Computer Scientist." :)
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.
ReplyDeleteSome time will be needed to pass before evaluating the importance of the break-through.
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.