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 language | English (US) |
|---|---|
| Pages (from-to) | 268-292 |
| Number of pages | 25 |
| Journal | Journal of the ACM |
| Volume | 43 |
| Issue number | 2 |
| DOIs | |
| State | Published - Mar 1996 |
| Externally published | Yes |
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver