A two prover one round game with strong soundness

Subhash Khot, Muli Safra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show that for any fixed prime q ≥ 5 and constant ζ > 0, it is NP-hard to distinguish whether a two prove 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 testis 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 in approximable within factor (log n) 1/6 - o(1).

Original languageEnglish (US)
Title of host publicationProceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Pages648-657
Number of pages10
DOIs
StatePublished - 2011
Event2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States
Duration: Oct 22 2011Oct 25 2011

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
CountryUnited States
CityPalm Springs, CA
Period10/22/1110/25/11

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A two prover one round game with strong soundness'. Together they form a unique fingerprint.

Cite this