Clique is hard to approximate within n1−ε
Open Access
- 1 January 1999
- journal article
- Published by International Press of Boston in Acta Mathematica
- Vol. 182 (1) , 105-142
- https://doi.org/10.1007/bf02392825
Abstract
Project Euclid - mathematics and statistics onlineThis publication has 26 references indexed in Scilit:
- Free Bits, PCPs, and Nonapproximability---Towards Tight ResultsSIAM Journal on Computing, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- Linearity testing in characteristic twoIEEE Transactions on Information Theory, 1996
- Improved non-approximability resultsPublished by Association for Computing Machinery (ACM) ,1994
- Efficient probabilistically checkable proofs and applications to approximationsPublished by Association for Computing Machinery (ACM) ,1993
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,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
- Trading group theory for randomnessPublished by Association for Computing Machinery (ACM) ,1985