Interactive proofs and the hardness of approximating cliques

TLDR

The paper aims to link clique approximation to multi‑prover interactive proofs and to construct an efficient multi‑prover proof system for NP. The authors build an efficient multi‑prover interactive proof for NP that uses few random and communication bits, establish a connection between clique approximation and such proofs, and prove correctness of a multilinearity test. The connection shows that approximating the largest clique size is hard, yielding new hardness results.

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.