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.

## 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