Journal of the ACM Bibliography

Abstract

The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interactive proofs is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: F.1.3 [Computation by Abstract Devices]: Complexity Classes -- reducibility and completeness, relations among complexity classes; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Hardness of approximation, independent set in a graph, multilinearity testing, \emph{np-completeness}, probabilistically checkable proofs

Selected papers that cite this one

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998.

• Sanjeev Arora and Madhu Sudan. Improved low degree testing and its applications. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 485-495, El Paso, Texas, 4-6 May 1997.

• Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and nonapproximability -- towards tight results. SIAM Journal on Computing, 27(3):804-915, June 1998.

• Anne Condon, Joan Feinberg, Carsten Lund, and Peter Shor. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2):369-400, April 1997.

• Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57(2):187-199, October 1998.

• David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246-265, March 1998.

• Howard Karloff and Uri Zwick. A 7/8-approximation algorithm for MAX 3SAT? In 38th Annual Symposium on Foundations of Computer Science, pages 406-415, Miami Beach, Florida, 20-22 October 1997. IEEE.

• Ashwin Nayak, Alistair Sinclair, and Uri Zwick. Spatial codes and the hardness of string folding problems (extended abstract). In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 639-648, San Francisco, California, 25-27 January 1998.

• Uri Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 201-210, San Francisco, California, 25-27 January 1998.

Selected references

• Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; a new characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 21-31, New Orleans, Louisiana, 6-8 May 1991.

• Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 113-131, Chicago, Illinois, 2-4 May 1988.

• Bonnie Berger and John Rompel. A better performance guarantee for approximate graph coloring. Algorithmica, 5:459-466, 1990.

• Piotr Berman and Georg Schnitger. On the complexity of approximating the independent set problem. Information and Computation, 96(1):77-94, January 1992.

• Benny Chor and Oded Goldreich. On the power of two-point based sampling. Journal of Complexity, 5(1):96-106, March 1989.

• Anne Condon and Richard J. Lipton. On the complexity of space bounded interactive proofs (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 462-467, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete (preliminary version). In 32nd Annual Symposium on Foundations of Computer Science, pages 2-12, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• Uriel Feige and Adi Shamir. Multi-oracle interactive protocols with constant space verifiers. Journal of Computer and System Sciences, 44(2):259-271, April 1992.

• Katalin Friedl, Zsolt Hátsági, and Alexander Shen. Low-degree tests. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 57-64, Arlington, Virginia, 23-25 January 1994.

• M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. Journal of the ACM, 23(1):43-49, January 1976.

• Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):691-729, July 1991.

• David S. Johnson. The NP-completeness column: An ongoing guide: The tale of the second prover. Journal of Algorithms, 13(3):502-524, September 1992.

• Nati Linial and Umesh Vazirani. Graph products and chromatic numbers. In 30th Annual Symposium on Foundations of Computer Science, pages 124-128, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, October 1992.

• Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960-981, September 1994.

• Burkhard Monien and Ewald Speckenmeyer. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica, 22(1):115-123, 1985.

• Alessandro Panconesi and Desh Ranjan. Quantifiers and approximation (extended abstract). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 446-456, Baltimore, Maryland, 14-16 May 1990.

• Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425-440, December 1991.

• Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, October 1992.

• Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729-735, October 1983.

Shortcuts: