A Counterexample to Strong Parallel Repetition

DOI10.1137/090747270zbMath1234.68141OpenAlexW1979615282WikidataQ124938821 ScholiaQ124938821MaRDI QIDQ3093622

Ran Raz

Publication date: 18 October 2011

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

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

zbMATH Keywords

odd cycle gameparallel repetition theoremtwo-prover games

Mathematics Subject Classification ID

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

Related Items (12)

Anchored Parallel Repetition for Nonlocal Games ⋮ Semi-quantum money ⋮ An integer parallelotope with small surface area ⋮ Interactions of computational complexity theory and mathematics ⋮ Communication and information complexity ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ Information value of two-prover games ⋮ Dimension Reduction for Polynomials over Gaussian Space and Applications ⋮ Pointer chasing via triangular discrimination ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Communication Complexity of Statistical Distance ⋮ Unnamed Item

This page was built for publication: A Counterexample to Strong Parallel Repetition