TY - GEN
T1 - A 3-query non-adaptive PCP with perfect completeness
AU - Khot, Subhash
AU - Saket, Rishi
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=34247534691&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34247534691&partnerID=8YFLogxK
U2 - 10.1109/CCC.2006.5
DO - 10.1109/CCC.2006.5
M3 - Conference contribution
AN - SCOPUS:34247534691
SN - 0769525962
SN - 9780769525969
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 159
EP - 169
BT - Proceedings - Twenty-First Annual IEEE Conference on Computational Complexity, CCC 2006
T2 - 21st Annual IEEE Conference on Computational Complexity, CCC 2006
Y2 - 16 July 2006 through 20 July 2006
ER -