tag:blogger.com,1999:blog-3722233.post112465650151435011..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: More on parallel repetition (by Ryan O'Donnell)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1124810051982936822005-08-23T10:14:00.000-05:002005-08-23T10:14:00.000-05:00Please go over #1. The benefit from repetition in...Please go over #1. The benefit from repetition in this case is exponential.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1124751659641600452005-08-22T18:00:00.000-05:002005-08-22T18:00:00.000-05:00I'm not very familiar with Ran's theorem, but if s...I'm not very familiar with Ran's theorem, but if so few people understand it it might be well worth going over it again in detail.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1124743879322877382005-08-22T15:51:00.000-05:002005-08-22T15:51:00.000-05:00I must be missing something, but I thought Raz's r...I must be missing something, but I thought Raz's result was only needed for multi-prover interactive proofs, not PCPs. Can someone explain further?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1124735755758263712005-08-22T13:35:00.000-05:002005-08-22T13:35:00.000-05:00Presumably part of the reason it's not an easily a...Presumably part of the reason it's not an easily approachable result is because people haven't approached it much. A catch-22. If people push there way through it, and then do their best to exposit it, and then this process is repeated enough times, I think almost any result can be made much more sensible. Perhaps it's being percieved as some mystifying technical result is part of the problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1124724466263413052005-08-22T10:27:00.000-05:002005-08-22T10:27:00.000-05:00I don't think you can use Feige-Lovasz because the...I don't think you can use Feige-Lovasz because the answer size is too large so you cannot apply the long-code (you get an exponential size proof).<BR/>As for Feige-Killian I think it depends on the applicationAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1124695452099525272005-08-22T02:24:00.000-05:002005-08-22T02:24:00.000-05:00I'd say 3, if it were me. The idea is to make sure...I'd say 3, if it were me. The idea is to make sure you and the students at least understand this technique in detail. Then in a future year, if you want to attempt 1 (or heavens, even a follow-up course - "PCP 202") you have some appreciation for what is different.<BR/><BR/>Keep in mind, though, that I don't know either result at all. This is just going by what you've said.Anonymousnoreply@blogger.com