Computer Science/Discrete Mathematics Seminar II

Topic: Parallel Repetition for 3-Player XOR Games
Speaker: Yang Liu
Affiliation: Institute for Advanced Study
Date: April 16, 2024

In a 3-𝖷𝖮𝖱 game , the verifier samples a challenge (x,y,z)∼μ where μ is a probability distribution over Σ×Γ×Φ, and a map t:Σ×Γ×Φ→ for a finite Abelian group  defining a constraint. The verifier sends the questions x, y and z to the players Alice, Bob and Charlie respectively, receives answers f(x), g(y) and h(z) that are elements in  and accepts if f(x)+g(y)+h(z)=t(x,y,z). The value, 𝗏𝖺𝗅(), of the game is defined to be the maximum probability the verifier accepts over all players' strategies.

We show that if  is a 3-𝖷𝖮𝖱 game with value strictly less than 1, whose underlying distribution over questions μ does not admit Abelian embeddings into (ℤ,+), then the value of the n-fold repetition of  is exponentially decaying. That is, there exists c=c() greater than 0 such that 𝗏𝖺𝗅(⊗n) less than or equal to 2−cn. This extends a previous result of [Braverman-Khot-Minzer, FOCS 2023] showing exponential decay for the GHZ game. Our proof combines tools from additive combinatorics and tools from discrete Fourier analysis.

Based on joint work with Amey Bhangale, Mark Braverman, Subhash Khot, Dor Minzer.