tag:blogger.com,1999:blog-3722233.comments2018-03-23T08:37:54.866-04:00Computational ComplexityLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger22060125tag:blogger.com,1999:blog-3722233.post-39968972241286844992018-03-14T20:50:14.659-04:002018-03-14T20:50:14.659-04:00a true celebritya true celebrityAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42419988837164263362018-03-12T20:13:16.244-04:002018-03-12T20:13:16.244-04:00I should note that RJL had a change of heart when ...I should note that RJL had a change of heart when it struck us that any P=NP proof must embody a proof of strong circuit lower bounds, yet no strategies ever proposed seem to give any sign of awareness of this need: https://rjlipton.wordpress.com/2017/12/08/pnp-perhaps-i-change-my-mind/ (We still both believe factoring is classically tractable though.)KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78584326994384412262018-03-08T17:48:04.487-05:002018-03-08T17:48:04.487-05:00When I turn on the History channel and they are pl...When I turn on the History channel and they are playing The Hunt for Red October, it is their right but it also frustrates a potentially non-trivial number of their viewers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32872484262592251682018-03-08T11:26:22.118-05:002018-03-08T11:26:22.118-05:00Anonymous12:25 to be constructive, perhaps readers...Anonymous12:25 to be constructive, perhaps readers (including you) could send guest CCC blog posts that Lance and Bill would include (after review) in their blog? After all this is their blog site; so it is definitely their prerogative to post what they feel is appropriate. space2001noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14976024413128008792018-03-08T00:25:11.639-05:002018-03-08T00:25:11.639-05:00What does any of this have to do with Computationa...What does any of this have to do with Computational Complexity (or Theory CS more generally)?<br /><br />I feel like this blog is increasingly just your and Bill's personal soapboxes and if so maybe it should be rebranded that way and not as the CCC blogAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31717165057016941982018-03-06T07:28:54.028-05:002018-03-06T07:28:54.028-05:00No, I didn't get any compensation for this pos...No, I didn't get any compensation for this post or the car. I still haven't asked for my deposits back from Tesla. No good reason to unless Tesla looks like it's going bankrupt. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87636365758472171302018-03-05T05:20:12.649-05:002018-03-05T05:20:12.649-05:00Here's a new tool to find natural pangrams htt...Here's a new tool to find natural pangrams https://wordsmith.org/pangram/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83841850401702754192018-03-03T11:20:03.847-05:002018-03-03T11:20:03.847-05:00What happens to the $1000 deposit you paid Tesla? ...What happens to the $1000 deposit you paid Tesla? Do you get it back?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17967418874507783562018-03-02T10:54:20.476-05:002018-03-02T10:54:20.476-05:00Sponsored ads on my CC Blog?! Unsubscribing.Sponsored ads on my CC Blog?! Unsubscribing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37013116274393689162018-02-26T00:15:57.706-05:002018-02-26T00:15:57.706-05:00Fixed- thanks.
When I first wrote it, it was inten...Fixed- thanks.<br />When I first wrote it, it was intention- not an insult, I think I got it from a novelty song to the tune of Modern Major General (or to the tune of The Elements if you prefer) that rhymed President with<br />Resident and refered to the prez as the current resident. But its still wrong and confusing so I corrected it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56199542079324656112018-02-26T00:02:24.896-05:002018-02-26T00:02:24.896-05:00Isnt there a "p" missing from "curr...Isnt there a "p" missing from "current resident"? (I guess this wasn't meant as a pun)domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32616503062506491552018-02-25T22:30:36.564-05:002018-02-25T22:30:36.564-05:00First: Ted Cruz was not born in this country and h...First: Ted Cruz was not born in this country and he ran for president anyway. Second: When I told my class that it is undecidable to tell if a program has an infinite loop or not, someone said if that if that were really so, the TA wouldn't be able to grade their homework. (Valid point.) - Mike GoodrichUnknownhttps://www.blogger.com/profile/14681318770774754133noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63844566377120916282018-02-25T17:13:42.698-05:002018-02-25T17:13:42.698-05:00Fixed, thanks
bill g.Fixed, thanks<br />bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85906160934443544452018-02-25T17:09:19.865-05:002018-02-25T17:09:19.865-05:00Isnt there a "b" missing as second argum...Isnt there a "b" missing as second argument of the second UNION in 3) Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55651811230171371042018-02-25T01:58:27.172-05:002018-02-25T01:58:27.172-05:00Meanwhile, my 8-years efforts for P vs NP:
http:/...Meanwhile, my 8-years efforts for P vs NP:<br /><br />http://vixra.org/abs/1801.0100YShttp://vixra.org/abs/1801.0100noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2265892308415480032018-02-25T01:11:53.113-05:002018-02-25T01:11:53.113-05:00Meanwhile, my 8-years efforts for P vs NP:
http:...Meanwhile, my 8-years efforts for P vs NP:<br /><br /> http://vixra.org/abs/1801.0100Unknownhttps://www.blogger.com/profile/13699450530150796472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82955771557520688842018-02-24T18:15:36.540-05:002018-02-24T18:15:36.540-05:00What I find curious about NPI is that we _know_ it...What I find curious about NPI is that we _know_ it is non-empty, assuming P ≠ NP. On the other hand, under the same assumption, we are unable to prove that any *natural* problem is in NPI. Andras Faragohttp://www.utdallas.edu/~faragonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89791162684659227522018-02-23T23:01:11.038-05:002018-02-23T23:01:11.038-05:00If you haven't already, there has been a recen...If you haven't already, there has been a recent breakthrough regarding UGC, see<br />Subhash Khot, Dor Minzer, and Muli Safra:<br /><a href="https://eccc.weizmann.ac.il/report/2018/006/" rel="nofollow">Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion.</a> Electronic Colloquium on Computational Complexity (ECCC) 25: 6 (2018)<br /><br />Changed my view from "agnostic" to "almost certainly true".Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20052699630081184742018-02-23T22:51:05.146-05:002018-02-23T22:51:05.146-05:00I find the existence of NP-Intermediate problems j...I find the existence of NP-Intermediate problems just as obvious as P ≠ NP. Consider Graph Isomorphism. (On a side note, I don't think Babai's breakthrough is progress towards showing GI is in P but the converse!) If it in P, then it would be insane. On a side note, I conjuncture that is not in BQP either. And by the beautiful result of Boppana, Hastad and Zachos, if GI is NP-Complete than the polynomial hierarchy collapses. (I know, I know, using the fact that polynomial hierarchy is infinite to give evidence that P ≠ NP is circular but think about it!)<br /><strong>Proving</strong> that a problem is NP-Intermediate is insanely hard, because it is (as you mentioned) equivalent to proving P ≠ NP.Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52001360359194024142018-02-23T18:52:34.640-05:002018-02-23T18:52:34.640-05:00RW is Ryan Wiliams, EJ is Anonymous, but a specifi...RW is Ryan Wiliams, EJ is Anonymous, but a specific anonymous. Obviously I am not very inside, otherwise I would have talked about Alice and Bob instead. How to explain background to a question in few words, without getting complaints about all kinds of perceived misbehaviour? I don't know and don't care. I just ask what I want to know, and give some background if I believe that it is necessary or helpful.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42498893801656817262018-02-23T10:44:20.524-05:002018-02-23T10:44:20.524-05:00NP complete/hard problems are a contrived set beca...NP complete/hard problems are a contrived set because real world "noise" in problem formulation imposes an upper bound way before we would hit the computational upper bound especially given the massive hardware resources that are readily available at our fingertips. <br /><br />To take Euclidean TSP as one prototypical example (yes, there is a trivial factor-of-2 approximation), I do not know of a situation where one possesses perfect data for the edge costs across M sites (M>100 or whatever is the upper bound of the best TSP solver) to begin planning. By the time we traverse a small fraction of the computed plan (say a Lyft or Uber autonomous car picking up passengers), the subsequent costs would have changed significantly to require re-planning every so often. While the exact TSP solution has proven optimality, it may be very sub-optimal (fragile) when considering an ever changing environment.<br /><br />Despite optimal chip design being another prototypical NP hard instance we now have incredible chips that incorporate many billions of transistors without breaking a sweat (at least not mine :-)). <br /><br />While NSA would love to crack encrypted data, they probably have figured out alternative schemes to get what they need - in many, if not all situations.<br /><br />Chess, go and other games are already contrived in that no one really cares how well you can play on an ever increasing NxN board. space2001noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40567666619232246232018-02-23T09:17:09.567-05:002018-02-23T09:17:09.567-05:00is it a mega name drop level where they don't ...is it a mega name drop level where they don't just drop the name they drop the initials showing just how inside they are?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9502794643350870832018-02-23T05:45:36.446-05:002018-02-23T05:45:36.446-05:00"And we've seen no non-trivial algorithms..."And we've seen no non-trivial algorithms for general NP problems like circuit-SAT."<br /><br />What counts as a non-trivial algorithm? Does the simplex-algorithm count as a non-trivial algorithm? It works fine in practice, most of the time. Do the recent analog Max-SAT solvers (like <a href="https://arxiv.org/abs/1801.06620" rel="nofollow">this from 20 Jan 2018</a> or <a href="https://arxiv.org/abs/1710.09278" rel="nofollow">that</a> from <a href="http://memcpu.com/" rel="nofollow">MemComputing, Inc.</a> initially presented <a href="https://arxiv.org/abs/1512.05064" rel="nofollow">on 16 Dec 2015</a>) count as non-trivial algorithms? The inventors claim that it works fine in practice, but I admit that claims from startups should be taken with a grain of salt.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77248700999380990362018-02-23T05:25:08.754-05:002018-02-23T05:25:08.754-05:00Who is EJ? Who is RW? Are we supposed to guess? Who is EJ? Who is RW? Are we supposed to guess? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91830085390341847712018-02-22T20:20:34.253-05:002018-02-22T20:20:34.253-05:00There is plenty of (technical) stuff on wikipedia ...There is plenty of (technical) stuff on wikipedia that is just plain wrong...Anonymousnoreply@blogger.com