Clique is hard to approximate withinn ^1−ε

1. Arora, S., Lund, C., Motwani, R., Sudan, M. & Szegedy, M., Proof verification and the hardness of approximation problems, in33rd Annual IEEE Symposium on Foundations of Computer Science (Pittsburgh, PA, 1992), pp. 14–23. To appear inJ. ACM.

2. Arora, S. &Safra, S., Probabilistic checking of proofs: a new characterization of NP.J. ACM, 45 (1998), 70–122.

   Article  MathSciNet  MATH  Google Scholar 

3. Babai, L., Trading group theory for randomness, in17th Annual ACM Symposium on Theory of Computing (Providence, RI, 1985), pp. 420–429.

4. Babai, L., Fortnow, L., Levin, L. & Szegedy, M., Checking computations in polynomial time, in23rd Annual ACM Symposium on Theory of Computing (New Orleans, LA, 1991), pp. 21–31.

5. Babai, L., Fortnow, L. &Lund, C., Nondeterministic exponential time has two-prover interactive protocols.Comput. Complexity, 1 (1991), 3–40.

   Article  MathSciNet  MATH  Google Scholar 

6. Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M. &Sudan, M., Linearity testing in characteristic two.IEEE Trans. Inform. Theory, 42 (1996), 1781–1796.

   Article  MathSciNet  MATH  Google Scholar 

7. Bellare, M., Goldreich, O. &Sudan, M., Free bits PCPs and nonapproximability—towards tight results.SIAM J. Comput., 27 (1998), 804–915.

   Article  MathSciNet  MATH  Google Scholar 

8. Bellare, M., Goldwasser, S., Lund, C. & Russell, A., Efficient probabilistically checkable proofs and applications to approximation, in25th Annual ACM Symposium on Theory of Computing (San Diego, CA, 1993), pp. 294–304.

9. Bellare, M. & Sudan, M., Improved nonapproximability results, in26th Annual ACM Symposium on Theory of Computing (Montreal, 1994), pp. 184–193.

10. Ben-Or, M., Goldwasser, S., Kilian, J. & Wigderson, A., Multiprover interactive proofs. How to remove intractability, in20th Annual ACM Symposium on Theory of Computing (Chicago, IL, 1988), pp. 113–131.

11. Berman, P. &Schnitger, G., On the complexity of approximating the independent set problem.Inform. and Comput., 96 (1992), 77–94.

    Article  MathSciNet  MATH  Google Scholar 

12. Boppana, R. &Halldórsson, M., Approximating maximum independent sets by excluding subgraphs.BIT, 32 (1992), 180–196.

    Article  MathSciNet  MATH  Google Scholar 

13. Bourgain, J., Walsh subspaces ofL^p-product spaces, inSeminaire d'analyse fonctionnelle (1979–1980), pp. 4.1–4.9. École Polytechnique, Palaiseau, 1980.

    Google Scholar 

14. Cook, S. A., The complexity of theorem proving procedure, in3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151–158.

15. Feige, U., A threshold of lnn for approximating set cover, in28th Annual ACM Symposium on Theory of Computing (Philadelphia, PA, 1996), pp. 314–318. To appear inJ. ACM.

16. Feige, U. &Goemans, M., Approximating the value of two-prover proof systems, with applications to MAX 2SAT and MAX DICUT, in3rd Israel Symposium on the Theory of Computing and Systems (Tel Aviv, 1995), pp. 182–189. IEEE Comput. Soc. Press, Los Alamitos, CA, 1995.

    Google Scholar 

17. Feige, U., Goldwasser, S., Lovász, L., Safra, S. &Szegedy, M., Interactive proofs and the hardness of approximating cliques.J. ACM, 43 (1996), 268–292.

    Article  MathSciNet  MATH  Google Scholar 

18. Feige, U. & Kilian, J., Two prover protocols—Low error at affordable rates, in26th Annual ACM Symposium on Theory of Computing (Montreal, 1994), pp. 172–183.

19. Feige, U., Zero-knowledge and the chromatic number, in11th Annual IEEE Conference on Computational Complexity (Philadelphia, PA, 1996), pp. 278–287.

20. Fortnow, L., Rompel, J. & Sipser, M., On the power of multi-prover interactive protocols, in3rd IEEE Symposium on Structure in Complexity Theory (1988), pp. 156–161.

21. Garey, M. R. &Johnson, D. S.,Computers and Intractability. A Guide to the Theory of NP-completeness. W. H. Freeman, San Fransisco, CA, 1979.

    MATH  Google Scholar 

22. Goemans, M. & Williamson, D., 878-approximation algorithms for Max-Cut and Max-2-SAT, in26th Annual ACM Symposium on Theory of Computing (Montreal, 1994), pp. 422–431.

23. Goldwasser, S., Micali, S. &Rackoff, C., The knowledge complexity of interactive proof systems.SIAM J. Comput., 18 (1989), 186–208.

    Article  MathSciNet  MATH  Google Scholar 

24. Håstad, J., Testing of the long code and hardness for clique, in28th Annual ACM Symposium on Theory of Computing (Philadelphia, PA, 1996), pp. 11–19. ACM, New York, 1996.

    Google Scholar 

25. —, Clique is hard to approximate withinn ^1−ε in37th Annual IEEE Symposium on Foundations of Computer Science (Burlington, VT, 1996), pp. 627–636. IEEE Comput. Soc. Press, Les Alamitos, CA, 1996.

    Google Scholar 

26. Håstad, J., Some optimal in-approximability results, in29th Annual ACM Symposium on Theory of Computing (1997), pp. 1–10.

27. Johnson, D. S., Approximation algorithms for combinatorial, problems.J. Comput. System Sci., 9 (1974), 256–278.

    Article  MATH  MathSciNet  Google Scholar 

28. Lund, C., Fortnow, L., Karloff, H. &Nisan, N., Algebraic methods for interactive proof systems.J. ACM, 39 (1992), 859–868.

    Article  MathSciNet  MATH  Google Scholar 

29. Motwani, R. &Raghavan, P.,Randomized Algorithms. Cambridge Univ. Press, Cambridge, 1995.

    MATH  Google Scholar 

30. Papadimitriou, C.,Computational Complexity. Addison-Wesley, Reading, MA, 1994.

    MATH  Google Scholar 

31. Papadimitriou, C. &Yannakakis, M. Optimization, approximation and complexity classes,J. Comput. System Sci., 43 (1991), 425–440.

    Article  MathSciNet  MATH  Google Scholar 

32. Raz, R., A parallel repetition theorem.SIAM J. Comput. 27 (1998), 763–803.

    Article  MATH  MathSciNet  Google Scholar 

33. Shamir, A., IP=PSPACE.J. ACM, 39 (1992), 869–877.

    Article  MATH  MathSciNet  Google Scholar 

34. Zuckerman, D., On unapproximable versions of NP-complete problems.SIAM J. Comput., 25 (1996), 1293–1304.

    Article  MATH  MathSciNet  Google Scholar 

Download references