A 3-query non-adaptive PCP with perfect completeness

Subhash Khot, Rishi Saket

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

Abstract

We study a very basic open problem regarding the PCP characterization of NP, namely, the power of PCPs with 3 non-adaptive queries and perfect completeness. The lowest soundness known till now for such a PCP is 6/8 + ε given by a construction of Håstad [11]. However, Zwick [15] shows that a 3-query non-adaptive PCP with perfect completeness cannot achieve soundness below 5/8. In this paper, we construct a 3-query non-adaptive PCP with perfect completeness and soundness 20/27 + ε, which improves upon the previous best soundness of 6/8 + ε. A standard reduction from PCPs to constraint satisfaction problems (CSPs) implies that it is NP-hard to tell if a boolean CSP on 3-variables has a satisfying assignment or no assignment satisfies more than 20/27 + ε fraction of the constraints. Our construction uses "biased Long Codes" introduced by Dinur and Safra [6]. We develop new 3-query tests to check consistency between such codes. These tests are analyzed by extending Håstad's Fourier methods [11] to the biased case.

Original languageEnglish (US)
Title of host publicationProceedings - Twenty-First Annual IEEE Conference on Computational Complexity, CCC 2006
Pages159-169
Number of pages11
DOIs
StatePublished - 2006
Event21st Annual IEEE Conference on Computational Complexity, CCC 2006 - Prague, Czech Republic
Duration: Jul 16 2006Jul 20 2006

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
Volume2006
ISSN (Print)1093-0159

Other

Other21st Annual IEEE Conference on Computational Complexity, CCC 2006
Country/TerritoryCzech Republic
CityPrague
Period7/16/067/20/06

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'A 3-query non-adaptive PCP with perfect completeness'. Together they form a unique fingerprint.

Cite this