pdf icon
A Two-Prover One-Round Game with Strong Soundness
Received: July 2, 2012
Revised: May 7, 2013
Published: December 6, 2013
Download article from ToC site:
[PDF (308K)]    [PS (1180K)]    [PS.GZ (334K)]
[Source ZIP]
Keywords: approximation, approximation algorithms, Fourier transform, inapproximability, label cover, Grothendieck inequality, linearity testing, PCP, probabilistically checkable proofs
ACM Classification: F.1.3
AMS Classification: 68Q17

Abstract: [Plain Text Version]

We show that for any fixed prime $q \geq 5$ and constant $\zeta > 0$, it is NP-hard to distinguish whether a two-prover one-round game with $q^6$ possible answers has value at least $1-\zeta$ or at most $\frac{4}{q}$. The result is obtained by combining two techniques: (i) An Inner PCP based on the point versus subspace test for linear functions. The test is analyzed Fourier analytically. (ii) The Outer/Inner PCP composition that relies on a certain sub-code covering property for Hadamard codes. This is a new and essentially black-box method to translate a codeword test for Hadamard codes to a consistency test, leading to a full PCP construction.

As an application, we show that unless NP has quasi-polynomial time deterministic algorithms, the Quadratic Programming Problem is inapproximable within factor $(\log n)^{1/6 - o(1)}$.

A preliminary version of this paper appeared in the Proceedings of the 52nd IEEE FOCS, 2011.