- Undirected Connectivity in Log-Space by Omer Reingold
- Entropy Waves, the Zig-Zag Graph Product and New Constant Degree Expanders by Reingold, Salil Vadhan and Avi Wigderson
I consider Reingold's paper the second best result of the decade (after "Primes in P" which won the prize in 2006). Reingold settled a long-standing open question deterministically showing how to get from point A to point B in an undirected graph using memory equivalent to remembering a constant number of vertices.
The zig-zag paper developed a new construction of constant-degree expanders. We already had simpler expander constructions but the zig-zag technique gave us a recursive way to think about expanders that Reingold drew on for his paper.
This is the first Gödel prize for each of these authors and I'm especially happy to see Wigderson, perhaps the best complexity theorist of our generation, take the prize. Avi could have easily won it earlier for his work on zero-knowledge, derandomization, circuit complexity or many other topics.
Congrats to All!
A notable aspect about the papers mentioned in this post is that two out of the three (Primes in P, and the zigzag paper) appears in a top math journal (Annals). The undirected s-t paper (i.e. the journal version) has not appeared yet (I was unable to locate it).
ReplyDeleteI think the journal choices for these papers are significant. It reinforces the feeling that the best
works of TCS are indeed a part of pure mathematics, and mathematicians are appreciative of the subject. It also indicates that the publishing culture (at least at the very top level) in TCS is moving closer to that of pure mathematics within which it rightfully belongs.
Lance, it would be more polite to link to publicly accessible versions of these papers.
ReplyDeleteReingold's paper appeared in JACM. That refutes the theory of the first anonymous.
ReplyDeleteOn another point, I think the Primes in P paper is vastly overrated. While definitely a major achievement, it has no applications even if we interpret "applications" as "connections to other areas of complexity theory". On the other hand, the zig-zags paper was beautiful in its own right and also served as the basis and/or inspiration for several subsequent important works.
To Anon 1:
ReplyDeleteThe Annals is a journal that publishes excellent and important research (as judged by its editorial board) in ALL areas of mathematics -- pure and applied. Of course, the best applied mathematics papers tend to be theoretical as well, with the usual definition-theorem-proof format (if that's what you mean by "pure" mathematics.)
At any rate, a subject that proves theorems IS a branch of mathematics, and there is no need to feel insecure about the place of theoretical computer science in the grand mathematical scheme.
Is it a conflict of interest that the chair of the committee was the advisor of one of the recipients?
ReplyDeleteIs there any such thing as a conflict of interest when it comes to choosing awardees for major prizes?
the usual definition-theorem-proof format (if that's what you mean by "pure" mathematics.)
ReplyDeleteYes, thats what I meant by "pure mathematics". I had no intention to downplay "applied math".
At any rate, a subject that proves theorems IS a branch of mathematics, and there is no need to feel insecure about the place of theoretical computer science in the grand mathematical scheme.
Its not a question of feeling "insecure", but my point is rather as a branch of mathematics, TCS should also adhere to the mainstream mathematical traditions and standards with regards to publishing etc. Also, more effort could be made to integrate ourselves in the larger mathematical community by participating more vigorously in activities of societies such as the AMS. I see very few TCS-ists in AMS sectional/national meetings, and most TCS people seems uninterested in organizing AMS Special Sessions regularly. Doing these things will help TCS to be more in harmony with the rest of mathematical community.
Everyone has favorites that "should have" gotten the award. Anon3 thinks Primes-in-P is overrated, I feel that Smoothed-analysis is beautiful but hasn't really revolutionized our way of thinking/analyzing algorithms. A paper that I feel has decidedly revolutionized the way we think about probabilistic computation is Luca Trevisan's extractor construction. I am surprised that Luca hasn't won the Gödel Prize for this work.
ReplyDeleteThe prime problem is much more important and better known than s-t problem. The class P is much more natural than LOGSPACE. The primality result inspire a lot of work in polynomial identity testing. How come prime in P is overrated compared to s-t in LOGSPACE? I am surprised by the taste of anon3.
ReplyDelete> The primality result inspire a lot
ReplyDelete> of work in polynomial identity
> testing.
I thought it was the other way around: that earlier work on identity testing inspired the Primes in P techniques.
Undirected st-connectivity in logspace has been published in 2008 in JACM and not in 2007.
ReplyDeleteThe prime problem is much more important and better known than s-t problem. The class P is much more natural than LOGSPACE. The primality result inspire a lot of work in polynomial identity testing. How come prime in P is overrated compared to s-t in LOGSPACE? I am surprised by the taste of anon3.Regardless of the importance of each problem, I believe that polynomial time is a complex, obscure and mathematically much uglier concept than space bounded computation. If by natural you mean "elegant" (as it is common in mathematical literature) then I don't see your point. If by natural you refer to some superficial connection to real world, then I'd suggest to think again about the status of general polynomial time as a concept. Although, it's a big discussion, I'd say that logspace (and space bounded in general) is much more "practically robust" - it appears much closer to reality.
ReplyDeleteI agree with some anon who said ppl have their own choices. Personally I liked "Primes is in P" paper more than Reingold's paper. But don't mis-understand me, I really like them both. No offense, I found it stupid that "Primes is in P" is overrated, whats even the basis for deciding what is overrated?
ReplyDeleteAlso, get over the TCS and "pure math" stuff... TCS is good, if you enjoy it, just enjoy it, and stop fantasizing about it being math, math being art, and blah blah blah...
Also, get over the TCS and "pure math" stuff... TCS is good, if you enjoy it, just enjoy it, and stop fantasizing about it being math, math being art, and blah blah blah...It's not a psychological question ("get over it"). And it's not an emotional question ("enjoy it"; should we enjoy things in order to have an opinion on them at all?)
ReplyDeleteIt's an intellectually important question whether TCS is a part of pure mathematics or not. Your comment has no relevance to this question.
Why is s-t connectivity in LOGSPACE such a surprising result. It is clear that it is in NLOGSPACE. You have to just guess the next vertex, and so on.
ReplyDelete