Parallel Repetition for the GHZ Game: Exponential Decay

Mark Braverman, Subhash Khot, Dor Minzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PublisherIEEE Computer Society
Pages1337-1341
Number of pages5
ISBN (Electronic)9798350318944
DOIs
StatePublished - 2023
Event64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, United States
Duration: Nov 6 2023Nov 9 2023

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Country/TerritoryUnited States
CitySanta Cruz
Period11/6/2311/9/23

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Abelian Embeddings
  • Additive Combinatorics
  • Analysis of Boolean functions
  • GHZ game
  • Parallel Repetition

Fingerprint

Dive into the research topics of 'Parallel Repetition for the GHZ Game: Exponential Decay'. Together they form a unique fingerprint.

Cite this