Parallel Repetition of the Odd Cycle Game

DOI10.1007/978-3-540-78773-0_58zbMATH Open1136.68407OpenAlexW1543591046MaRDI QIDQ5458570FDOQ5458570

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

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

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)

Cites Work

• Communication Complexity
• Title not available (Why is that?)
• A Parallel Repetition Theorem
• Title not available (Why is that?)
• Amortized Communication Complexity
• Perfect parallel repetition theorem for quantum XOR proof systems
• The communication complexity of enumeration, elimination, and selection

Cited In (8)

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

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)