Interactive proofs and approximation: reductions from two provers in one round
- 30 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- On the success probability of the two provers in one-round proof systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fully parallelized multi prover protocols for NEXP-timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximating clique is almost NP-completePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The complexity of the max word problem and the power of one-way interactive proof systemscomputational complexity, 1993
- Efficient probabilistically checkable proofs and applications to approximationsPublished by Association for Computing Machinery (ACM) ,1993
- On the hardness of approximating minimization problemsPublished by Association for Computing Machinery (ACM) ,1993
- Two-prover one-round proof systemsPublished by Association for Computing Machinery (ACM) ,1992
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Checking computations in polylogarithmic timePublished by Association for Computing Machinery (ACM) ,1991
- Multi-prover interactive proofs: how to remove intractabilityPublished by Association for Computing Machinery (ACM) ,1988