Parallel Repetition for the GHZ Game: Exponential Decay
Mark Braverman, Subhash Khot, Dor Minzer
2023Year
2Citations
4Top-tier citations
Abstract
We show that the value of the n-fold repeated GHZ game is at most , 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.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 8e942cb1-c64f-4b38-974c-e7edcb31241aCited by top-tier papers4
- Strong Bounds for 3-ProgressionsZander Kelley, Raghu MekaFOCS 2023 · 24 citations
- On Approximability of Satisfiable k-CSPs: IVAmey Bhangale, Subhash Khot, Dor MinzerSTOC 2024 · 2 citations
- An Analytical Approach to Parallel Repetition via CSP Inverse TheoremsAmey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu et al.STOC 2026
- Parallel Repetition for 3-Player XOR GamesAmey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu et al.STOC 2025
Builds on2
Related papers
- Polynomial-Time Tolerant Testing Stabilizer StatesSrinivasan Arunachalam, Arkopal DuttSTOC 2025 · 4 citations
- Quasipolynomial Bounds for the Corners TheoremMichael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni et al.FOCS 2025 · 2 citations
- Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic ApproachSaeed Mehraban, Mehrdad TahmasbiSTOC 2024 · 2 citations
- Hedging in games: Faster convergence of external and swap regretsXi Chen, Binghui PengNeurIPS 2020 · 88 citations
- A near-optimal quadratic Goldreich-Levin algorithm (extended abstract)Jop Briët, Davi Castro-SilvaSODA 2026 · 1 citation
