A two prover one round game with strong soundness

Add to your list(s) Download to your calendar using vCal

• Khot, S (Courant Institute)
• Wednesday 30 March 2011, 15:30-16:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Discrete Analysis

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

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.