Theory of Computing
-------------------
Title     : A Two-Prover One-Round Game with Strong Soundness
Authors   : Subhash Khot and Muli Safra
Volume    : 9
Number    : 28
Pages     : 863-887
URL       : https://theoryofcomputing.org/articles/v009a028

Abstract
--------

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