tag:blogger.com,1999:blog-3722233.post5872825090146585881..comments2023-12-05T20:28:02.861-06:00Comments on Computational Complexity: A few more notes about Sipser and Sipser-60thLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-23530403381939893532014-11-05T11:17:39.823-06:002014-11-05T11:17:39.823-06:00Will you tell us a little bit about the contents o...Will you tell us a little bit about the contents of the talks ?Pascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45013261984532087552014-11-03T16:42:44.733-06:002014-11-03T16:42:44.733-06:00No Bill, I was not kidding. And I only had one gla...No Bill, I was not kidding. And I only had one glass of wine at that point. <br /><br />Every new surprising algorithm we discover should be consider as evidence towards equality. I was surprised by some of the holographic algorithms. Avi W. pointed out once that these can be explained away by some argument that have to do with quantum computation. Still, the algorithms are surprising.<br /><br />Perhaps Barrington's theorem is the first example of this. That was a real shocker to all of us that were trying to prove exactly the opposite. <br /><br />So I would say, as much as we haven't made much progress on the lower bound front, I am not sure we have done much progress on the upper bound front either.<br /><br />And Bill, it was great to see you and to be able to chat with you.<br />Mauricio Karchmerhttps://www.blogger.com/profile/07790098127188054941noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61710318288751024652014-11-03T14:32:27.725-06:002014-11-03T14:32:27.725-06:00I got an email asking if I got Karchmer's quot...I got an email asking if I got Karchmer's quote backwards.<br />No- he really did say that thel ower bounds we want are false and that we don't have algorithms because we are stupid, Of course, he may have been kidding.<br /><br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-237329470995277462014-11-03T12:27:07.649-06:002014-11-03T12:27:07.649-06:00STEVE RUDICH DOES NOT [THING] WE ARE SIX MONTHS AW...STEVE RUDICH DOES NOT [THING] WE ARE SIX MONTHS AWAY FROM AN IND PROOF FOR P VS NP.<br />However, Mauricio now [things] that (1) We can't prove lower bounds because they are false, and (2) we can't prove upper bounds because we are stupid.Anonymousnoreply@blogger.com