INTERACTIVE PROOFS AND THE HARDNESS OF APPROXIMATING CLIQUES

The contribution of this paper is two-fold. First, a connection is est ablished between approximating the size of the largest clique in a gra ph and multi-prover interactive proofs. Second, an efficient multi-pro ver interactive proof for NP languages is constructed, where the verif ier uses very few random bits and communication bits. Last, the connec tion between cliques and efficient multi-prover interactive proofs, is shown to yield hardness results on the complexity of approximating th e size of the largest clique in a graph. Of independent interest is ou r proof of correctness for the multilinearity test of functions.