Parallel Repetition of the Odd Cycle Game

DOI10.1007/978-3-540-78773-0_58MaRDI QIDQ5458570zbMATH OpenOpenAlexFDO

Authors Kooshiar Azimian, Mario Szegedy

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78773-0_58

zbMATH Keywords

parallel repetitionCHSHtwo prover games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) 2-person games (91A05) Complexity of proofs (03F20)

Recommendations

• A counterexample to strong parallel repetition
• Parallel repetition: simplification and the no-signaling case
• Parallel repetition in projection games and a concentration bound
• Parallel repetition of entangled games
• Strong Parallel Repetition Theorem for Free Projection Games

Cites work

• scientific article; zbMATH DE number 5485476 (Why is no real title available?)
• scientific article; zbMATH DE number 1559552 (Why is no real title available?)
• A Parallel Repetition Theorem
• Amortized Communication Complexity
• Communication Complexity
• Perfect parallel repetition theorem for quantum XOR proof systems
• The communication complexity of enumeration, elimination, and selection

Cited in

(8)

• The oriented cycle game
• Odd and even cycles in maker-breaker games
• Multiplayer parallel repetition for expanding games
• The structure of winning strategies in parallel repetition games
• Parallel repetition: simplification and the no-signaling case
• Information value of two-prover games
• The Game of Cycles
• The space complexity of mirror games

This page was built for publication: Parallel Repetition of the Odd Cycle Game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458570)