In 2010 this blog announced the following
Breakthrough!!!! results:
(Listed chronologically.)
-
Better Algorithms for Unique Games,
by Arora, Barak, Steurer. (We refer to this as AUG.)
-
Better Circuit Lower Bounds,
by Williams. (We refer to this as CLB.)
-
Erdos Distance Problem mostly resolved,
by Guth and Katz. (We refer to this as ED.)
-
Progress on
Density Needed to Guarantee a 3-AP,
by Sanders. (We refer to this as 3AP.)
-
Better Approximation Algorithm
for (a version of) Metric TSP,
by Gharan, Saberi, Singh. (We refer to this as TSP.)
Some of the comments on those posts questioned if these results really were
breakthroughs. This is a fair question; however, in order to answer it
the question arises
What is a breakthrough?
I list some criteria.
I'm not sure how many of these a breakthrough needs.
-
The result is correct and the paper is posted. This is mandatory.
-
The problem that the result concerns has to be important.
This might be subjective.
-
There has to be substantial progress on the problem.
This could be a matter of debate.
-
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,
smart folks say its hard.
So, how do the five breakthrough results look with these criteria?
I will now do the very silly exercise of actually giving numeric
values to these criteria. The scale is 1 to 10.
I do not take these numbers seriously; however, being forced to
assign numbers forces one to think about the criteria.
-
AUG: The Unique Game Conjecture is important, hence progress on it
in either direction is important.
The result was surprising since it may indicate that UGC is not true.
IMPORTANT: 8. PROGRESS: 8. THOUGHT HARD: 8.
TOTAL SCORE: 24.
-
CLB:
If you view this as an attack on P vs NP then the problem being considered is important
but the progress on it is not impressive in absolute terms.
However, it is very impressive in terms of getting around current barriers.
IMPORTANT: 10. PROGRESS: 8. THOUGHT HARD: 10.
TOTAL SCORE: 28.
-
ED is certainly very interesting, but is it important?
There is a
website devoted to it
but does that make it important?
It has lead to mathematics of importance but that's not quite the same thing.
The result makes substantial progress in that it SOLVED the problem
(up to a log factor).
Smart people thought the proof would require new techniques. It did.
IMPORTANT: 6. PROGRESS: 10. THOUGHT HARD: 9.
TOTAL SCORE: 25.
-
3AP is certainly important and has lead to important mathematics.
But there are people working in complexity, even complexity bloggers,
who do not think this sort of thing
is important. They are wrong. Hold the flames- I am kidding.
The progress made is more one of technique then result.
Many people thought it was hard.
IMPORTANT: 7. PROGRESS: 7. THOUGHT HARD: 9.
TOTAL SCORE: 23.
-
TSP:
The metric TSP problem has had that constant of 3/2 for a very long time.
It was possible that 3/2 was optimal.
Getting any kind of improvement on it, even a very tiny one, would be very important
and would be real progress.
Alas the paper didn't quite do that--- it made progress on a version of the problem.
Still impressive. I will leave it to people in algorithms to argue if it is
a breakthrough or not.
-
In November I heard about the result of
on Network flows
by
Christiano, Kelner, Madry, Spielma, Teng.
I had heard that it was a breakthrough.
I emailed 5 friends in algorithms
asking if they wanted to guest post on it. Nobody wanted to.
This is NOT a statement about the paper itself.
Reasons were a combination of
(a) too busy, (b) don't know the area well enough, and
(c) don't want to deal with the idiotic comments your
blog often gets.
This does NOT mean it was not a breakthrough.
It may have to do with my choice of friends.
Was it a breakthrough? I still don't know.
However, I will now open it up: If someone wants to guest blog
about it, let me know.
These are my opinions. What are yours? On these results or on any other ones?
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.
ReplyDeleteOn item 6, you forgot Shang-Hua Teng on your author list. Also, 'Christano' should be 'Christiano'.
ReplyDeleteAndy D- Thanks, I have fixed it.
ReplyDeleteAn "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?
ReplyDeleteI'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.
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.
ReplyDeleteFor better or for worse, the current definition of "breakthrough" in the TCS community seems to be "was discussed in a blog post".
ReplyDeleteI agree with Eppstein. These multiple exclamation blog posts are really cringe-inducing and embarrassing to the whole community, sadly.
ReplyDeleteFirst 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.
ReplyDeleteMost theoretical computer scientists agree that approximation algorithms are important.
ReplyDeleteSeveral 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.
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.
ReplyDelete-Warren
The first half of the post- the
ReplyDeletecriteria, is an attempt at beginning an intelligent discussion of the issue
The second half- actually rating the recent alleged breakthroughs,
is of course (as I said in the post)
very silly. I did it just to se
what would happen.
YES, the ratings are in general way to high with one exception.
Erdos-Distance problem really was solved,
so that gets a very high rating for
progress on the problem
.
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.
ReplyDeleteThe 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?
"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..."
ReplyDeleteIf 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. ;)
I propose the formation of a new discipline, "breakthrough studies".
ReplyDeleteOne 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.
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.
Most theoretical computer scientists agree that approximation algorithms are important. There are many reasons for this, that are beyond the scope of this post.
ReplyDeleteMost 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.
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.
ReplyDeleteE.g., Arora, Barak, Steurer.
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.
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.
Anonymous proposes: ... minor breakthroughs ... major breakthroughs ... monumental breakthroughs ...
ReplyDeleteDuh ... 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 Theory of Communication, for example.
Maybe we should call them ... "epochal" breakthroughs? :)
This hair-splitting reminds me irresistibly of the US Homeland Security's Advisory System ... hmmm ... how well did *that* work out?
It seems to me that Terry Tao's way of thinking works better:
----------------
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 undefinable 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.
----------------
Very plausibly, in 2010 there were some Tao-style "on to something" breakthroughs ... yet history suggests that we will come to an appreciation of them only slowly.
you became like people magazine. i wonder how much lower this blog can go
ReplyDeleteGASARCH proposes: What is a breakthrough? Lets have an intelligent discussion.
ReplyDeleteAnonymous responds: You became like people magazine. i wonder how much lower this blog can go.
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 (here is a GASARCH commentary from 2007, for example).
That the CT blogosphere is the last word is, of course, expected by nobody:
------------
Tell all the Truth but tell it slant --
Success in Circuit lies
Too bright for our infirm Delight
The Truth's superb surprise
— Dickinson
------------
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.
Give us more, please!
Above you said that Erdos Distance really was solved. Isn't it currently at O(n/sqrt(log n))≥g(n)≥Ω(n/log n)?
ReplyDeleteErdos Distance Problem: YES, I mispoke (mistyped?) - I should have
ReplyDeletesaid solved within-a-log-factor
or something of that sort.
Still very impressive.
I've also seen it stated as
showing that g(n) \ge n^{2-ep}
for all ep>0. So THAT version has been solved.
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.
ReplyDeleteFirst, 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.
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.
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.
Which of the papers above should be called a breakthrough will be more clear in a few years, I think.
To those who sneer at the value of epsilon, I wonder whether they would be impressed by 4/3 as opposed to 3/2.
ReplyDeleteI think everyone would be more impressed by 4/3 than 3/2 - 10^{-13}, which is the approximation ratio claimed by this paper.
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.
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.
ReplyDeleteAside 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.