Skip to main navigation Skip to search Skip to main content

Interactive proofs and the hardness of approximating cliques

  • Uriel Feige
  • , Shafi Goldwasser
  • , Laszlo Lovasz
  • , Shmuel Safra
  • , Mario Szegedy

Research output: Contribution to journal › Article › peer-review

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. Of independent interest is our proof of correctness for the multilinearity test of functions.

Original languageEnglish (US)
Pages (from-to)268-292
Number of pages25
JournalJournal of the ACM
Volume43
Issue number2
DOIs
StatePublished - Mar 1996
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Interactive proofs and the hardness of approximating cliques'. Together they form a unique fingerprint.

Cite this