Error reduction by parallel repetition - a negative result

DOI10.1007/S00493-002-0001-0zbMATH Open1017.68052OpenAlexW3179843568MaRDI QIDQ1397480FDOQ1397480

Authors: Oleg Verbitsky, Uriel Feige 

Publication date: 6 August 2003

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-002-0001-0

Recommendations

• A Parallel Repetition Theorem
• Parallel repetition of two-prover one-round games: an exposition
• scientific article; zbMATH DE number 1263221
• Two-Prover Protocols---Low Error at Affordable Rates
• A counterexample to strong parallel repetition

zbMATH Keywords

error reduction

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Multistage and repeated games (91A20)

Cited In (10)

• A \(k\)-provers parallel repetition theorem for a version of no-signaling model
• A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence
• Parallel repetition of two-prover one-round games: an exposition
• Parallel repetition of computationally sound protocols revisited
• A parallel repetition theorem for entangled projection games
• Anchored parallel repetition for nonlocal games
• Communication and information complexity
• Distinguishing distributions using Chernoff information
• Parallel repetition via fortification: analytic view and the quantum case
• Derandomized parallel repetition theorems for free games

This page was built for publication: Error reduction by parallel repetition - a negative result

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