More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP

Samorodnitsky and Trevisan [STOC 2000, pp. 191–199] proved that there exists, for every positive integer k , a PCP for NP with O (log n ) randomness, query complexity 2 k + k 2 , free bit complexity 2 k , completeness 1 ‐ ϵ , and soundness 2   ‐ k   2+ ϵ . In this article, we devise a new “outer verifier,” based on the layered label cover problem recently introduced by Dinur et al. [STOC 2003, pp. 595–601], and combine it with a new “inner verifier” that uses the query bits more efficiently than earlier verifiers. Our resulting theorem is that there exists, for every integer f ≥ 2, every positive integer t ≤ f ( f ‐ 1)/2, and every constant ϵ > 0, a PCP for NP with O (log n ) randomness, query complexity f + t , free bit complexity f , completeness 1 ‐ ϵ , and soundness 2 ‐ t + ϵ . As a corollary, there exists, for every integer q ≥ 3 and every constant ϵ > 0, a q ‐query PCP for NP with amortized query complexity 1 + $ 1 + \sqrt{2/q} + \varepsilon $ + ϵ . This improves upon the result of Samorodnitsky and Trevisan with respect to query efficiency, i.e., the relation between soundness and the number of queries. Although the improvement may seem moderate—the construction of Samorodnitsky and Trevisan has amortized query complexity 1 + 2/ $ 1 + 2/\sqrt{q} + \varepsilon $ —we also show in this article that combining our outer verifier with any natural candidate for a corresponding inner verifier gives a PCP that is less query efficient than the one we obtain.© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008