Two-Prover Protocols---Low Error at Affordable Rates

DOI10.1137/S0097539797325375zbMath0959.68112OpenAlexW2013821228MaRDI QIDQ4507353

Joe Kilian, Uriel Feige

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539797325375

zbMATH Keywords

interactive proof systemscomplexity theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Anchored Parallel Repetition for Nonlocal Games ⋮ The complexity of approximating a nonlinear program ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ Unnamed Item ⋮ A parallel repetition theorem for entangled projection games