Parallel Repetition for the GHZ Game: Exponential Decay

2022/11/24 by Mark Braverman, Subhash Khot, Braverman, Mark +3 · 3 citations
Computer Science · Economics, Econometrics and Finance · #Artificial Intelligence in Games #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Game Theory and Voting Systems

paper · pdf · doi:10.48550/arxiv.2211.13741

openalex publication_date 2022/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the value of the n-fold repeated GHZ game is at most 2^-Ω(n), improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

Cited by

• The Lens of Abelian Embeddings
• Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
• Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

Related

• Parallel Repetition for the GHZ Game: A Simpler Proof
• A Parallel Repetition Theorem for the GHZ Game
• Parallel Repetition for 3-Player XOR Games
• Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs
• Parallel Repetition For All 3-Player Games Over Binary Alphabet