tag:blogger.com,1999:blog-3722233.post790319176368165958..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Breaking WallsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-56046518168360850172009-11-12T16:21:42.459-06:002009-11-12T16:21:42.459-06:00Also... shameless plug alert... twenty years on, t...Also... shameless plug alert... twenty years on, the ideas are still bearing fruit. See, e.g., Theorem 4.3 of <a href="http://www.cs.dartmouth.edu/~ac/Pubs/icalp09anno.pdf" rel="nofollow">this paper</a> (pdf).AChttps://www.blogger.com/profile/14911233583375020356noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11383521095713234842009-11-12T16:17:14.855-06:002009-11-12T16:17:14.855-06:00I like teaching LFKN first (to introduce "ari...I like teaching LFKN first (to introduce "arithmetization"), and then Shamir the next day. And randomized PIT goes sometime before LFKN.AChttps://www.blogger.com/profile/14911233583375020356noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29082181421923004212009-11-12T12:53:10.629-06:002009-11-12T12:53:10.629-06:00In my opinion, the characterization IP = PSPACE is...In my opinion, the characterization IP = PSPACE is due to your paper with Lund, Karloff and Nisan, and Shamir.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35166102956812481442009-11-12T09:59:32.202-06:002009-11-12T09:59:32.202-06:00Perfect timing, Lance. I had just mentioned some o...Perfect timing, Lance. I had just mentioned some of this history in my Complexity Theory class yesterday; I have now asked my students to checkout your post.aravindhttp://www.cs.umd.edu/~srinnoreply@blogger.com