Parallel Repetition for k-Player XOR GamesResearch Paper
Parallel repetition is the standard way to amplify the soundness of multi-prover interactive protocols without adding players or rounds. A verifier plays copies of a one-round game at once and accepts only if every copy is won. The basic question is how fast the optimal winning probability falls with . This matters for probabilistically checkable proofs…