Interactive proofs and the hardness of approximating cliques

1996/03/01 by Uriel Feige, Shafi Goldwasser, Laszlo Lovász +5 · 12 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Advanced Graph Theory Research

paper · pdf · doi:10.1145/226643.226652

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

Cited by

• A threshold of ln <i>n</i> for approximating set cover
• 3-Query RLDCs are Strictly Stronger than 3-Query LDCs
• Homomorphism Testing with Resilience to Online Manipulations
• The extended Smale's 9th problem -- On computational barriers and\n paradoxes in estimation, regularisation, computer-assisted proofs and\n learning
• A Proof Checking View of Parameterized Complexity
• Topologies of Stochastic Markov Models: Computational Aspects
• The Lens of Abelian Embeddings
• Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
• Near Optimal Hardness of Approximating k-CSP
• The quantum smooth label cover problem is undecidable
• Average-Case Complexity of Quantum Stabilizer Decoding
• New Tools and Connections for Exponential-Time Approximation. [europepmc]

Related

• A Polynomial Time Algorithm For Solving Clique Problems
• On P Versus NP
• Multi-Clique-Width
• Proof of Concept: Fast Solutions to NP-problems by Using SAT and Integer\n Programming Solvers
• Constant Approximating k-Clique is W[1]-hard