Parallel Repetition From Fortification
Apr 8, 2015
Two-prover games are fundamental to theoretical computer science. Their applications range from cryptography to probabilistically checkable proofs to quantum computing. The parallel repetition theorem analyzes repeated two prover games, and is notorious for its difficulty. In this work we give a simple transformation on games -- "fortification" -- and show that for fortified games a parallel repetition theorem holds with ideal parameters. Our proof is combinatorial and (extremely) short. As corollaries, we obtain simple combinatorial proofs of state-of-the-art PCP Theorems.