Direct Products and Parallel Repetition
summary
Proves an exponential parallel-repetition bound for projection games with entanglement: if the entangled value is 1 − ε then the k-fold repeated entangled value falls like (1 − Ω(ε^4))^k, obtained by recasting games as linear operators and introducing a vector-valued relaxation (val+) that is multiplicative and approximates the game value. Proof uses a collision value and a rounding/quantum correlated-sampling step (embezzlement) to convert high val+ into an actual strategy. Also describes using de-randomized parallel repetition for PCP gap amplification and implications for set-cover hardness.
AI-written summary · about