Towards an optimal query efficient PCP?

Subhash Khot, Muli Safra, Madhur Tulsiani

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

Abstract

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16. At a technical level, our main contribution is constructing a new outer PCP which is "robust" against bounded degree polynomials, and showing that it can be composed with the hyper-graph linearity test with 3 free queries. We believe this outer PCP may be useful in obtaining the optimal query vs. soundness tradeoff for PCPs.

Original languageEnglish (US)
Title of host publicationITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science
Pages173-186
Number of pages14
DOIs
StatePublished - 2013
Event2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 - Berkeley, CA, United States
Duration: Jan 9 2013Jan 12 2013

Publication series

NameITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

Other

Other2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013
CountryUnited States
CityBerkeley, CA
Period1/9/131/12/13

Keywords

  • CSPs
  • PCPs
  • hardness of approximation

ASJC Scopus subject areas

  • Management of Technology and Innovation
  • Computer Science (miscellaneous)

Fingerprint Dive into the research topics of 'Towards an optimal query efficient PCP?'. Together they form a unique fingerprint.

Cite this