tag:blogger.com,1999:blog-3722233.post1466372859387524486..comments2021-04-20T09:52:56.297-05:00Comments on Computational Complexity: Gödel PrizeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-73388300974980005982009-08-03T10:05:59.596-05:002009-08-03T10:05:59.596-05:00Why is s-t connectivity in LOGSPACE such a surpris...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5906350520099496442009-06-01T13:41:04.735-05:002009-06-01T13:41:04.735-05:00Also, get over the TCS and "pure math" stuff... TC...<I>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...</I>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?)<br /><br />It's an intellectually important question whether TCS is a part of pure mathematics or not. Your comment has no relevance to this question.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65906725241881557282009-05-25T06:54:06.634-05:002009-05-25T06:54:06.634-05:00I agree with some anon who said ppl have their own...I 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?<br /><br />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...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57521690406729978792009-05-22T11:03:44.035-05:002009-05-22T11:03:44.035-05:00The prime problem is much more important and bette...<I>The 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.</I>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55756583315745580782009-05-22T00:16:51.337-05:002009-05-22T00:16:51.337-05:00Undirected st-connectivity in logspace has been pu...Undirected st-connectivity in logspace has been published in 2008 in JACM and not in 2007.Thiru Vijayaraghavanhttp://www.cmi.ac.in/~vijay/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33101218894042030262009-05-21T17:31:15.826-05:002009-05-21T17:31:15.826-05:00> The primality result inspire a lot
> of w...> The primality result inspire a lot <br />> of work in polynomial identity <br />> testing. <br /><br />I thought it was the other way around: that earlier work on identity testing inspired the Primes in P techniques.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70688297229051911102009-05-21T17:23:12.202-05:002009-05-21T17:23:12.202-05:00The prime problem is much more important and bette...The 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82272393460953553972009-05-21T15:30:17.276-05:002009-05-21T15:30:17.276-05:00Everyone has favorites that "should have" gotten t...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.PolySizedStatisticalTestnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30076088527170898722009-05-21T14:50:19.181-05:002009-05-21T14:50:19.181-05:00the usual definition-theorem-proof format (if that...<I>the usual definition-theorem-proof format (if that's what you mean by "pure" mathematics.)<br /></I>Yes, thats what I meant by "pure mathematics". I had no intention to downplay "applied math".<br /><br /><I>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.<br /></I>Its not a question of feeling "insecure", but my point is rather <I>as a branch of mathematics</I>, 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76938251249156854452009-05-21T14:32:36.250-05:002009-05-21T14:32:36.250-05:00Is it a conflict of interest that the chair of the...Is it a conflict of interest that the chair of the committee was the advisor of one of the recipients?<br /><br />Is there any such thing as a conflict of interest when it comes to choosing awardees for major prizes?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88119253627022196872009-05-21T14:26:51.696-05:002009-05-21T14:26:51.696-05:00To Anon 1:
The Annals is a journal that publishes...To Anon 1:<br /><br />The 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.) <br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8363877042886982402009-05-21T13:55:47.658-05:002009-05-21T13:55:47.658-05:00Reingold's paper appeared in JACM. That refutes th...Reingold's paper appeared in JACM. That refutes the theory of the first anonymous.<br /><br />On 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50026458349757925452009-05-21T11:41:09.591-05:002009-05-21T11:41:09.591-05:00Lance, it would be more polite to link to publicly...Lance, it would be more polite to link to publicly accessible versions of these papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58507517700076028082009-05-21T10:55:02.417-05:002009-05-21T10:55:02.417-05:00A notable aspect about the papers mentioned in thi...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).<br /><br />I think the journal choices for these papers are significant. It reinforces the feeling that the best<br />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.Anonymousnoreply@blogger.com