Questions / discussion about the course
The comments section of this post is for questions, comments, and discussion about the lectures.
posted by Ryan O'Donnell at 11:45 AM
Home page: http://www.cs.washington.edu/education/courses/533/05au/
posted by Ryan O'Donnell at 11:45 AM
3 Comments:
Does the parralel repetition theorem hold only for 2-player 1-round game, or any interactive proof system as in IP?
Hey Prasad. For k-player 1-round games, I don't know if the parallel repetition theorem is explicitly known to hold. An example due to Ran Raz (see Appendix A of the Feige survey I mentioned), generalizing Feige's NA counterexample, demonstrates that if it does hold, the parameter s' would also need to depend on k, in addition to s and |A|.
My feeling is that probably it is not too much *extra* work to repeat Raz's proof for k players -- I would *guess* that it probably holds (with some dependence on k, as mentioned).
For multi-round games, I don't think anything is known.
I got this doubt, as I was scribing the lecture.. Do we really need to use Self Correction in the assignment tester? Cant we just argue that the value of L(s) read from the table L is correct with probability 1-delta, otherwise anyway L will be delta far from a linear function. It might make the analysis more messy though.
Post a Comment
<< Home