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

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorics in computer science (68R05) 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

(14)

• Towards the parallel repetition conjecture
• A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence
• A parallel repetition theorem for entangled projection games
• A k-provers parallel repetition theorem for a version of no-signaling model
• Derandomized parallel repetition theorems for free games
• Parallel repetition of computationally sound protocols revisited
• A Parallel Repetition Theorem
• Parallel repetition via fortification: analytic view and the quantum case
• Distinguishing distributions using Chernoff information
• Anchored parallel repetition for nonlocal games
• Parallel repetition of two-prover one-round games: an exposition
• Communication and information complexity
• On parallel repetition of PCPs
• Block rigidity: strong multiplayer parallel repetition implies super-linear lower bounds for Turing machines

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)