Parallel Repetition in Projection Games and a Concentration Bound

DOI10.1137/080734042zbMath1235.68078OpenAlexW2086423976MaRDI QIDQ3225175

Anup Rao

Publication date: 15 March 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080734042

zbMATH Keywords

concentrationparallel repetitionCHSH game

Mathematics Subject Classification ID

Cooperative games (91A12) 2-person games (91A05) Multistage and repeated games (91A20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Anchored Parallel Repetition for Nonlocal Games ⋮ Interactive Information Complexity ⋮ Max-3-Lin over non-abelian groups with universal factor graphs ⋮ A Characterization of Perfect Strategies for Mirror Games ⋮ Unnamed Item ⋮ Communication and information complexity ⋮ Flexible constrained de Finetti reductions and applications ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ Information complexity and applications. ⋮ Dimension Reduction for Polynomials over Gaussian Space and Applications ⋮ Optimality of Correlated Sampling Strategies ⋮ Perfect strategies for non-local games ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Communication Complexity of Statistical Distance ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence

This page was built for publication: Parallel Repetition in Projection Games and a Concentration Bound