Interactive proofs and the hardness of approximating cliques

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 ra...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 1996-03, Vol.43 (2), p.268-292
Main Authors: FEIGE, U, GOLDWASSER, S, LOVASZ, L, SAFRA, S, SZEGEDY, M
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Approximation
Complexity
Computer languages
Computer science
Computer science
control theory
systems
Construction
Exact sciences and technology
Graphs
Hardness
Information retrieval. Graph
Interactive
Languages
Programming theory
Studies
Theoretical computing
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 interaction 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.
ISSN:0004-5411
1557-735X
DOI:10.1145/226643.226652