Error reduction by parallel repetition - a negative result

DOI10.1007/S00493-002-0001-0MaRDI QIDQ1397480zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(10)

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

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)