Friday, November 11, 2005

Questions / discussion about the course

The comments section of this post is for questions, comments, and discussion about the lectures.

3 Comments:

Anonymous Anonymous said...

Does the parralel repetition theorem hold only for 2-player 1-round game, or any interactive proof system as in IP?

3:10 PM  
Blogger Ryan O'Donnell said...

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.

4:15 PM  
Anonymous Anonymous said...

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.

10:40 AM  

Post a Comment

<< Home