Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
Authors:
- 1 January 2006
- book chapter
- Published by Springer Nature
- p. 226-237
Abstract
No abstract availableKeywords
This publication has 22 references indexed in Scilit:
- Gowers uniformity, influence of variables, and PCPs2006
- Approximating Maximum Clique by Removing SubgraphsSIAM Journal on Discrete Mathematics, 2004
- A Parallel Repetition TheoremSIAM Journal on Computing, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- On Unapproximable Versions of $NP$-Complete ProblemsSIAM Journal on Computing, 1996
- Interactive proofs and the hardness of approximating cliquesJournal of the ACM, 1996
- Testing of the long code and hardness for clique1996
- Two prover protocols1994
- Efficient probabilistically checkable proofs and applications to approximations1993