More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP
2008 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 33, no 4, 497-514 p.Article in journal (Refereed) Published
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 2k + k(2), free bit complexity 2k, completeness 1 - epsilon, and soundness 2(-k2) + epsilon. 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 epsilon > 0, a PCP for NP with O(log n) randomness, query complexity f + t, free bit complexity f, completeness 1 - epsilon, and soundness 2(-t) + epsilon. As a corollary, there exists, for every integer q >= 3 and every constant epsilon > 0, a q-query PCP for NP with amortized query complexity 1 + root 2/q + epsilon-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 kess query efficient than the one we obtain.
Place, publisher, year, edition, pages
2008. Vol. 33, no 4, 497-514 p.
probabilistic proof systems, maximum CSP, approximation hardness
IdentifiersURN: urn:nbn:se:kth:diva-33173DOI: 10.1002/rsa.20226ISI: 000260844400005ScopusID: 2-s2.0-60349121066OAI: oai:DiVA.org:kth-33173DiVA: diva2:413776
QC 201104292011-04-292011-04-292011-04-29Bibliographically approved