Non-deterministic exponential time has two-prover interactive protocols
By László Babai, Lance Fortnow, Carsten Lund. Computational Complexity, 2005
506 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/b2521c1153f7b7649b0d1115b78bdaa42086f65d
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Oded Goldreich
- John Watrous
- Paul Valiant
- Richard Cleve
- Russell Impagliazzo
- Valentine Kabanets
- B. Toner
- Peter Høyer
In Computational Theory and Mathematics
- Oded Goldreich
- Paul Valiant
- Richard Cleve
- John Watrous
- Russell Impagliazzo
- Valentine Kabanets
- B. Toner
- Peter Høyer
Citations in the corpus
- Consequences and limits of nonlocal strategies (2004, background): “Babai, Fortnow, and Lund [4] proved that every language in NEXP has a two-prover interactive proof system.”
- Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency (2008, background): “2 A third major approach for improving the efficiency of proofs, arguably the most historically successful, is that of adding interaction between the prover and verifier[11, 15, 3].”
- Improved Delegation of Computation using Fully Homomorphic Encryption (2010, unknown): “The MIP=NEXP Theorem [ BFL91 ] and its scaled-down version by Babai et al. [BFLS91] yield multiprover interactive proofs and probabilistically checkable proofs for time T computations with a prover running in time poly(T ) and a verifier running in time poly(n, log T ), exactly as we want.”
- Introduction to Property Testing (2017, methodology): “The PCP Theorem itself is a culmination of a sequence of works, starting with Babai, Fortnow, and Lund [29], who showed that (unrestricted) PCPs (which are merely restricted by the verification time) captured the class NEXP, continuing with the different “scale downs”61 of that result to the poly-lo”
- Quantum Computational Complexity (2008, unknown): “NEXP A promise problem A = (Ayes, Ano) is in NEXP if and only if there exists an exponential-time non-deterministic Turing machine N for A. PL NC P NP PP BPP MASZK AM PSPACE EXP”
- Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds (2003, background): “The importance of this problem is witnessed by a plethora of its applications to perfect matching [35, 37, 14], equivalence testing of read-once branching programs [10], multiset equality testing [11], primality testing [1, 2], a number of complexity-theoretic results on probabilistically checkable ”