We show that for any fixed prime q ≥ 5 and constant ζ >; 0, it is NP-hard to distinguish whether a two prover one round game with q 6 answers has value at least 1 - ζ 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) .
No takes yet. Share an insight, caveat, or question.
Khot et al. (2011) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: