BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A two prover one round game with strong soundness - Khot\, S (Cour
 ant Institute)
DTSTART:20110330T143000Z
DTEND:20110330T153000Z
UID:TALK30465@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We show that for any large integer q\, it is NP-hard to distin
 guish 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 techn
 iques: (i) An Inner PCP based on the "point versus subspace" test for line
 ar functions. The test is analyzed Fourier analytically. (ii) The Outer/In
 ner PCP composition that relies on a certain "sub-code covering" property 
 for Hadamard codes.\n\nAs an application\, we show that unless NP has quas
 i-polynomial time deterministic algorithms\, the Quadratic Programming Pro
 blem is inapproximable within factor (log n)^{1/6 - o(1)}.\n\nThe talk sho
 uld be self-contained.\n\nJoint work with Muli Safra\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR