Revised: May 7, 2013

Published: December 6, 2013

**Keywords:**approximation, approximation algorithms, Fourier transform, inapproximability, label cover, Grothendieck inequality, linearity testing, PCP, probabilistically checkable proofs

**Categories:**complexity theory, inapproximability, PCP, probabilistically checkable proofs, approximation algorithms, Fourier transform, label cover, Grothendieck inequality, linearity testing, special issue, Boolean special issue

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