Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- 1 June 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 27 (3) , 804-915
- https://doi.org/10.1137/s0097539796302531
Abstract
No abstract availableThis publication has 38 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Multi-prover Encoding Schemes and Three-prover Proof SystemsJournal of Computer and System Sciences, 1996
- Eigenvalues and expansion of regular graphsJournal of the ACM, 1995
- Derandomized graph productscomputational complexity, 1995
- The hardness of approximation: Gap locationcomputational complexity, 1994
- Randomness in interactive proofscomputational complexity, 1993
- The complexity of the max word problem and the power of one-way interactive proof systemscomputational complexity, 1993
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- On approximation problems related to the independent set and vertex cover problemsDiscrete Applied Mathematics, 1984