ComputingComputer ScienceMathematicsParallel AlgorithmsParallel ComputingTheory Of ComputationProof ComplexityProof TheoryTheorem ProvingError ReductionParallel RepetitionProof SystemsRandomized Proof SystemsTwo-prover One-round Proof Systems
We characterize the power of two-prover one-round (MIP(2,1)) proof systems, showing that MIP(2,1)=NEXPTIME. However, the following intriguing question remains open: Does parallel repetition decrease the error probability of MIP(2,1) proof systems?.
13
Random walks, universal traversal sequences, and the complexity of maze problems
Romas Aleliunas, Richard M. Karp, Richard J. Lipton et al. · 1979 · 705 citations
Multi-prover interactive proofs: how to remove intractability
Michael Ben-Or, Shafi Goldwasser, Joe Kilian · 1988 · 484 citations
Approximating clique is almost NP-complete
Uriel Feige, S. Goldwasser, László Lovász et al. · 2002 · 397 citations