A 3-Query Non-Adaptive PCP with Perfect Completeness
Subhash Khot, Rishi Saket · 2006
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 + epsi given by a construction of Hastad (1997). However, Zwick (1998) 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 + epsi, which improves upon the previous best soundness of 6/8 + epsi. 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 + epsi fraction of the constraints. Our construction uses "biased long codes" introduced by Dinur and Safra (2002). We develop new 3-query tests to check consistency between such codes. These tests are analyzed by extending Hastad's Fourier methods (1997) to the biased case