Interactive proofs and the hardness of approximating cliques
- 1 March 1996
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 43 (2) , 268-292
- https://doi.org/10.1145/226643.226652
Abstract
No abstract availableKeywords
This publication has 18 references indexed in Scilit:
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- IP = PSPACEJournal of the ACM, 1992
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1992
- Multi-oracle interactive protocols with constant space verifiersJournal of Computer and System Sciences, 1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- A better performance guarantee for approximate graph coloringAlgorithmica, 1990
- Improving the performance guarantee for approximate graph coloringJournal of the ACM, 1983
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976