2026-07-23T20:14:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27048 2026-07-23T11:36:18Z ddc:004 open_access

Improved Parallel Repetition for GHZ-Supported Games via Spreadness Liu, Yang P. Lovett, Shachar Mittal, Kunal Parallel Repetition GHZ Game Algebraic Spreadness We prove that for any 3-player game G, whose query distribution has the same support as the GHZ game (i.e., all x,y,z ∈ {0,1} satisfying x+y+z = 0 (mod 2)), the value of the n-fold parallel repetition of G decays exponentially fast: val(G^{⊗ n}) ≤ exp(-n^c) for all sufficiently large n, where c > 0 is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant ε > 0, the probability that the players win at least a (3/4+ε) fraction of the n coordinates is at most exp(-n^c), where c = c(ε) > 0 is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order n^{-Ω(1)}. Our key technical tool is the notion of algebraic spreadness adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yang P. Liu and Shachar Lovett and Kunal Mittal 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.6 urn:nbn:de:0030-drops-270486 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.6 eng https://creativecommons.org/licenses/by/4.0/legalcode