tag:blogger.com,1999:blog-3722233.post113397054180631086..comments2019-09-21T10:58:30.930-04:00Comments on Computational Complexity: Surprising ResultsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger25125tag:blogger.com,1999:blog-3722233.post-1134256737869691672005-12-10T18:18:00.000-05:002005-12-10T18:18:00.000-05:00Janos makes many good suggestions, and indeed, the...Janos makes many good suggestions, and indeed, the theoretical ability to sort in linear time caused quite a stir when introduced. I don't agree that we must concentrate in techniques. A single isolated result can be surprising (like the median was many moons ago) or an entire new technique can catch us by suprise (the existence of zero knowledge proofs and PKC).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134232235700056832005-12-10T11:30:00.000-05:002005-12-10T11:30:00.000-05:00Did Janos meanLovasz Local Lemma or Szemeredi's re...Did Janos mean<BR/>Lovasz Local Lemma or <BR/>Szemeredi's regularity lemma?<BR/>I guess both have been extremely<BR/>useful.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134231059334201702005-12-10T11:10:00.000-05:002005-12-10T11:10:00.000-05:00Corrections and additions:Permanent is #P complete...Corrections and additions:<BR/><BR/>Permanent is #P complete did NOT introduce #P. The class was introduced in another paper of Valiant's "The complexity of Enumeration and Reliability Problems" (SICOMP 79, but, like the Permanent paper, published as a Tech Report earlier.) A close relative of #P, PP, was introduced by Gill in 74, and many combinnatorial counting problems related to it appear in my ICALP 77 paper.<BR/><BR/>Again, the linear time sorting seems to me much less BIG than the first sub-nlogn algorithm on RAMs (Willard..)<BR/><BR/><BR/>Other results that were BIG:<BR/>Planarity in linear time (Hopcroft and Tarjan) All bounded genus in linear time (Bohar) genus NP-hard.<BR/>Planarity in NC.<BR/><BR/>Space is better than time (SPACE(n/logn) contains linear time)<BR/>(Hopcroft, Paul, Valiant)<BR/><BR/>Undirected graph reachability in sub log^2 time. (Nisan et al)<BR/><BR/>Circuit depth is a version of communication complexity (Karchmer)<BR/><BR/>More generally, I think it is better to think of *techniques* that were new and surprising.<BR/><BR/>Let me toss out an initial random selection:<BR/><BR/>splay trees<BR/><BR/>amortized complexity<BR/><BR/>Kolmogorov techniques for proving lower bounds (Paul)<BR/><BR/>Underlying graph structure of computations to prove lower bounds (Valiant -- gave us superconcentrators and much more)<BR/><BR/>Isolation lemma (Vaziranis, Mulmuley)<BR/><BR/>Depth-first search (Hopcroft and Tarjan)<BR/><BR/>Bob and Alice's adventures in cryptoland (Blum, Goldwasser and Micali)<BR/><BR/>Good pseudorandom generators<BR/><BR/>PCP<BR/><BR/>PCP implies nonapproximability<BR/><BR/>Fourier analysis of Boolean functions<BR/><BR/>Szemeredi local lemma<BR/><BR/>......Janos Simonhttps://www.blogger.com/profile/15677985672817404601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134136677669362692005-12-09T08:57:00.000-05:002005-12-09T08:57:00.000-05:00Why don't we build a result-tree or a result-dag l...Why don't we build a result-tree or a result-dag like the complexity zoo and give weights to the node? After that, we can design our course based on this graph by DFS or WFS. We can also build a bipartite graph between results and methods(ideas). We can do it in a Wiki way.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134113012915241982005-12-09T02:23:00.000-05:002005-12-09T02:23:00.000-05:00In response to the anonymous post on Razborov's CL...In response to the anonymous post on Razborov's CLIQUE lower bound: it is still true that for slice functions, monotone and non-monotone complexities differ by a small polynomial (even less than quadratic). However,no one knows how to prove qudratic or better lower bounds on monotone complexity of an explicit slice function.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134103945214138992005-12-08T23:52:00.000-05:002005-12-08T23:52:00.000-05:00About plane TSP: Indeed shifting strategy used for...About plane TSP: Indeed shifting strategy used for plane TSP which was essentialy the main idea of this result was invented much earlier by Baker, and it is very unfortunate that the paper on plane TSP does not refer to Baker's (FOCS'83) paper and essentially ignores her result. I consider Baker's result a much bigger result.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134092746627097942005-12-08T20:45:00.000-05:002005-12-08T20:45:00.000-05:00Two other surprises from the 1980's: a. Razborov'...Two other surprises from the 1980's: <BR/><BR/>a. Razborov's superpolynomial lower bounds for monotone circuits computing CLIQUE. At the time, using slice function arguments, it appeared that monotone and nonmonotone complexities were within an additive quadratic term.<BR/><BR/>b. Barrington's proof that NC^1 is solvable using width-5 Branching Programs. At the time there were conjectures that MAJORITY was not efficiently solvable using only constant width.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134091865291523312005-12-08T20:31:00.000-05:002005-12-08T20:31:00.000-05:00I really enjoyed this post. I wonder if the author...I really enjoyed this post. I wonder if the authors can compile a similar list of <B>beautiful</B> results. Of course, beauty is in the eye of the beholder, but certain concepts are so simple and beautiful that we can explain them to a 10 year old. And beautiful results are almost always simple.<BR/><BR/>THe concept of undecidability is one such, in my opinion---you can explain it to anyone who knows how to write a program. Fermat's last theorem was another -- and in the words of Andrew Wiles himself, the beauty and simplicity of the theorem was what fascinated him and led him to work on it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134072665500491932005-12-08T15:11:00.000-05:002005-12-08T15:11:00.000-05:00What are the surprising results in theory?"I guess...What are the surprising results in theory?"<BR/><BR/>I guess that by "theory" Bill Gasarch meant "the theory of computing"; however, if one includes G�del incompleteness result, that speaks about decidability (in contrast to tractability), then it also seems appropriate to include a big surprise (if I'm not wrong) and certainly a very big result in itself: the independence of the Continuum Hypothesis from ZFC (P. Cohen 1963 [and (G�del 1938) that showed that CH is consistent with ZFC]).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134037400476579182005-12-08T05:23:00.000-05:002005-12-08T05:23:00.000-05:00In 22, under cryptographic assumptions, P=BPP is d...In 22, under cryptographic assumptions, P=BPP is due to Yao I think.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134000952370273672005-12-07T19:15:00.000-05:002005-12-07T19:15:00.000-05:00Interesting as always, but very skewed. What about...Interesting as always, but very skewed. What about other areas of computer science, like logic, cryptography, computational geometry, parallel and distributed computing? SZK is closed under complement, for a start.<BR/><BR/>The terminology is misleading. A result can't be called a surprise, let alone a "BIG surprise", if people weren't thinking along those terms. A conceptual advance, alright, but certainly not a surprise...<BR/><BR/>Rahul.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134000443364810852005-12-07T19:07:00.000-05:002005-12-07T19:07:00.000-05:00These are missing:Cache oblivious algorithms (Prok...These are missing:<BR/><BR/>Cache oblivious algorithms (Prokop et al. FOCS 1999)<BR/><BR/>Triangulation in linear time (Chazelle FOCS 1990).<BR/><BR/>Practical sorting in the unit cost RAM in o(n log n) time (Andersson FOCS 1996).<BR/><BR/>Poly-time certificates for primality (Miller??).<BR/><BR/>Existence of zero knowledge proofs.<BR/><BR/>Burrows-Wheeler transform for compression.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133989341557896322005-12-07T16:02:00.000-05:002005-12-07T16:02:00.000-05:00#15 is a fundamental result. It introduced a whole...#15 is a fundamental result. It introduced a whole new way to look at things, but it wasn't surprising in the sense that people were not thinking that the permanent was in poly-time. In fact most people hadn't even heard of the permanent.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133988391995446742005-12-07T15:46:00.000-05:002005-12-07T15:46:00.000-05:00Excellent post and discussion, everyone!Excellent post and discussion, everyone!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133981697346763882005-12-07T13:54:00.000-05:002005-12-07T13:54:00.000-05:00Siva's comments reflects the point that suprises a...Siva's comments reflects the point that suprises are a function of time. For example, in retrospect it's hard to understand why Godel's results were surprising. <BR/><BR/>By now we have gotten over the suprising fact that you can formally model computation, which I think is a BIG surprise.<BR/><BR/>The issue is that people have developed some intuition, and it told them that matrix multiplication is a simple problem and should have a simple complexity (indeed, this intuition is probably right and probably the right complexity is n^2) and if you think of the matrix as a linear function acting on vectors which has n^2 complexity, then it's really surprising that computing its output on $n$ independent vectors can be done faster than n^3.<BR/><BR/>Similarly, it seemed "obvious" that tossing coins helps speed up some algorithms. Now we may wonder why, and also how come it was not "obvious" that if there can be subexponential speedup then it's probably the case that BPP=P.<BR/><BR/>one addition is list decoding - it seemed obvious (not to mention proven) that you cannot decode binary codes with more than 25% errors, before people understood that they were asking the wrong question.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133981164798473592005-12-07T13:46:00.000-05:002005-12-07T13:46:00.000-05:00I don't know why you say (28) that GW was surprisi...I don't know why you say (28) that GW was surprising. It was beautiful and a big result to prove. But there was a conjecture by Poljak already for several years that the 5-cycle was the worst case for the so-called eigenvalue bound, which is equivalent to the SDP relaxation. So while it was a huge result to actually prove a good bound, I doubt it was surprising since the conjecture that there *was* a good, efficiently computable bound was around and was not due to GW.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133980346596531802005-12-07T13:32:00.000-05:002005-12-07T13:32:00.000-05:00With all due respect, most of the list isn't (and ...With all due respect, most of the list isn't (and shouldn't have been) surprising. Come on, how long had people been multiplying numbers more than 20 digits using computers, and how much effort had they invested in improving the quadratic-time algorithm? It was clever, decidedly cool, but people were SURPRISED by that? Shows to go how egotistic we are -- just because we couldn't conjure up ways to do something faster after a few minutes or few months of thinking (multiplication better than n^2, matrix multiplication faster than n^3, planar something without sorting, etc.), we are SURPRISED, and surprised BIG that it could be done?<BR/>Give me a break.<BR/><BR/>SivaD. Sivakumarhttps://www.blogger.com/profile/04674739621423058308noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133979337652306492005-12-07T13:15:00.000-05:002005-12-07T13:15:00.000-05:00You list "Connection between PCP and Approximation...You list "Connection between PCP and Approximation", but do not list the PCP theorem itself.<BR/><BR/>For me, the PCP theorem was the greatest (and probably the only) surprising result in complexity theory.edwardahirschhttps://www.blogger.com/profile/18094179693219521111noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133977514936836342005-12-07T12:45:00.000-05:002005-12-07T12:45:00.000-05:00The list is neat, but, of course, its content coul...The list is neat, but, of course, its content could well vary from person to person. Instead of suggesting inserts (and deletes), here is a suggestion: why not make an on-line poll ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133976394199721852005-12-07T12:26:00.000-05:002005-12-07T12:26:00.000-05:00LP is not stronly in P. Proving that it is strongl...LP is not stronly in P. Proving that it is strongly polynomial is still widely open.<BR/><BR/>Planar TSP was independently done by Mitchell at the same time.<BR/><BR/>I also think Cook theorem was independently done by Levin.<BR/><BR/>I doubt if most of those results would be remembered 20 years from now. The list is too long.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133975401625570492005-12-07T12:10:00.000-05:002005-12-07T12:10:00.000-05:00In 32 it should be: OleszkiewiczIn 32 it should be: Oles<B>z</B>kiewiczAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133975175994262232005-12-07T12:06:00.000-05:002005-12-07T12:06:00.000-05:00I might add another recent surprise: Cryptography ...I might add another recent surprise: Cryptography in NC^0 (Applebaum, Ishai, Kushilevitz).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133973849486324402005-12-07T11:44:00.000-05:002005-12-07T11:44:00.000-05:00Why 23 is not BIG? 22: randomness from hardness30:...Why 23 is not BIG? <BR/><BR/>22: randomness from hardness<BR/>30: hardness from randomnessAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133973558031158602005-12-07T11:39:00.000-05:002005-12-07T11:39:00.000-05:00What about the more recent (33) 2-Player Nash is P...What about the more recent <BR/><BR/>(33) 2-Player Nash is PPAD complete<BR/><BR/>(see Lance's post from a couple of days ago)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133972341043967872005-12-07T11:19:00.000-05:002005-12-07T11:19:00.000-05:00Nice list. Comments might reveal the precision and...Nice list. Comments might reveal the precision and recall...<BR/><BR/>Lance, your reference for (32) is wrong/inaccurate. It's Khot, Kindler, Mossel, O'Donnell. And in (31) it should be TSP in the plane (or Euclidean but not planar).<BR/><BR/>BTW, which direction of resolving the unique games conjecture will be considered surprising?<BR/><BR/>Robi.Anonymousnoreply@blogger.com