tag:blogger.com,1999:blog-3722233.post1381501092894849452..comments2019-06-26T08:34:34.605-04:00Comments on Computational Complexity: What Happened to the Surprising Theorems?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-141574588178313582019-06-21T18:44:42.473-04:002019-06-21T18:44:42.473-04:00I would say that the recent result of De Grey -- t...I would say that the recent result of De Grey -- that the chromatic number of the plane is at least 5 -- is shocking. In my opinion, all the evidence pointed to it being 4. Jeremy Almhttps://www.blogger.com/profile/13159920351819389963noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47725584784149140032019-06-08T23:34:33.059-04:002019-06-08T23:34:33.059-04:00"Shocking" may not be the right choice o..."Shocking" may not be the right choice of word here. Perhaps you meant "surprising" as in Lance's post.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34714759832907439622019-06-07T10:56:59.718-04:002019-06-07T10:56:59.718-04:00I also think that "Hadamard [and more recentl...I also think that "Hadamard [and more recently, DFT] isn't rigid" is quite shocking. It was a widely accepted guess that these are the most natural choices for proving rigidity.Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67397476733416223402019-06-07T10:50:42.016-04:002019-06-07T10:50:42.016-04:00I found Hastad's optimal inapproximability res...I found Hastad's optimal inapproximability results, especially the fact that MAX-3SAT can't be approximated beyond a random guess, quite shocking. Also all consequences of the UGC (e.g., GW Max-Cut algorithm, the trivial factor-2 vertex cover, etc, being all optimal), and especially Raghavendra's optimal algorithm for all CSPs. Soon we may see a proof of UGC, which would add another entry on the list of shocking results (when UGC was proposed, many thought it will be settled either way in the next conference, and nobody could foresee its power...).Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52125728626315618322019-06-07T04:04:09.248-04:002019-06-07T04:04:09.248-04:00Ewin Tang's killing of certain proclaimed &quo...Ewin Tang's killing of certain proclaimed "quantum speedups" by simulating those quantum algorithms using sophisticated classical sampling techniques was quite entertaining!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52103659970433542122019-06-06T22:03:55.266-04:002019-06-06T22:03:55.266-04:00Sure, those results could count as well.
I think...Sure, those results could count as well. <br /><br />I think the best example so far is Sanketh's. I didn't see it when I was posting initially, but I should have thought of it too! :) ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64769936627716053022019-06-06T19:51:59.112-04:002019-06-06T19:51:59.112-04:00@ryanw: I think I was shocked (mildly) by both the...@ryanw: I think I was shocked (mildly) by both the algorithms and the lower bounds for frequency moments in the streaming model (Alon, Matias, Szegedy, 1995). Before this paper came out, I think most theorists would've predicted that either all frequency moments are approximable in small space or none of them is. The paper showed -- through highly non-trivial ideas -- that F_0 and F_2 are approximable in logarithmic space, while higher moments need polynomial space.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42258933902392847862019-06-06T12:45:37.680-04:002019-06-06T12:45:37.680-04:00I agree with Anonymous, and I would also add that ...I agree with Anonymous, and I would also add that there are surprising analogues in Boolean complexity, namely the "hardness magnification" results. There's Allender-Koucky [JACM'10] which shows how n^{1.001} lower bounds can imply super-polynomial lower bounds, but also there are the recent papers:<br /><br />https://eccc.weizmann.ac.il/report/2018/199/<br />https://eccc.weizmann.ac.il/report/2018/139/<br />https://eccc.weizmann.ac.il/report/2018/158/<br />https://people.csail.mit.edu/rrw/MCSP-MKTP-stoc19.pdf<br /><br />An example theorem: From Razborov-Rudich, we believe there are no natural properties useful against P/poly, computable in P/poly. If we could even prove there are no such properties in N*poly(log N) size and poly(log N) depth, then already NP is not in P/poly.<br /><br />One could claim none of these are "shocking" because, if you expect the lower bounds to hold, the statements are of the form "True implies True". But the fact that such stuff is provable with existing complexity theory is pretty shocking to me. Hardness magnification shows in particular that there are good reasons why even weak lower bounds look out of reach: because they imply strong lower bounds!<br /><br />Results more along the lines of what Lance means by "shocking" would be the results on catalytic computation.<br />https://iuuk.mff.cuni.cz/~koucky/papers/cats.pdf<br />It's extremely counterintuitive to me that you can use a "dirty memory" to compute so much (and leave the dirty memory intact). <br /><br />Note that, in order to provide something that may be shocking, I had to cite an algorithmic result. It seems we are very pessimistic about what algorithms can do, so we're always shocked by algorithms but never by lower bounds. Can you think of any lower bound result you would be shocked by? ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69986724778136803672019-06-06T12:10:42.053-04:002019-06-06T12:10:42.053-04:00NEEXP in MIP*!!NEEXP in MIP*!!Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52616837974500638332019-06-06T12:02:28.029-04:002019-06-06T12:02:28.029-04:00I think homomorphic encryption was a major surpris...I think homomorphic encryption was a major surprise. I think crypto seems to produce surprises (maybe more so to outsiders) consistently...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68429149397211366622019-06-06T11:19:23.545-04:002019-06-06T11:19:23.545-04:00In algebraic complexity, recently we have seen a f...In algebraic complexity, recently we have seen a few fairly surprising theorem statements, chasm at depth four and three, and the recent bootstrapping results in polynomial identity testing (Agrawal, Ghosh, Saxena'18 ; Kumar, Saptharishi, Tengse'18) that shows a bare improvement of the trivial hitting set would lead to derandomization of polynomial identity testing. Anonymousnoreply@blogger.com