Proof verification and the hardness of approximation problems
- 1 May 1998
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 45 (3), 501-555
- https://doi.org/10.1145/278298.278306
Abstract
No abstract availableKeywords
This publication has 47 references indexed in Scilit:
- On the Hardness of Approximating the Chromatic NumberCombinatorica, 2000
- Linearity testing in characteristic twoIEEE Transactions on Information Theory, 1996
- On the Approximation of Maximum SatisfiabilityJournal of Algorithms, 1994
- PSPACE is provable by two provers in one roundJournal of Computer and System Sciences, 1994
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Arithmetization: A new method in structural complexity theorycomputational complexity, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976