Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-167 | 23rd November 2022 13:21

Parallel Repetition for the GHZ Game: Exponential Decay

RSS-Feed




TR22-167
Authors: Mark Braverman, Subhash Khot, Dor Minzer
Publication: 24th November 2022 00:17
Downloads: 518
Keywords: 


Abstract:

We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(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.



ISSN 1433-8092 | Imprint