skip to content

A two prover one round game with strong soundness

Presented by: 
S Khot [Courant Institute]
Wednesday 30th March 2011 - 15:30 to 16:30
INI Seminar Room 1
We show that for any large integer q, it is NP-hard to distinguish whether a two prover one round game with q^6 answers has value close to 1 or at most O(1/q). The result is obtained by combining two new 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.

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)}.

The talk should be self-contained.

Joint work with Muli Safra
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons