Three-query PCPs with perfect completeness over non-Boolean domains
2005 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 27, no 1, 46-75 p.Article in journal (Refereed) Published
We study non-Boolean PCPs that have perfect completeness and query three positions in the proof. For the case when the proof consists of values from a domain of size d for some integer constant d >= 2, we construct a nonadaptive PCP with perfect completeness and soundness d(-1) + d(-2) + epsilon, for any constant epsilon > 0, and an adaptive PCP with perfect cornpleteness and soundness d(-1) + epsilon, for any constant epsilon > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d(-1) + epsilon, for any constant epsilon > 0, where four positions are read from the proof. These results match the best known constructions for the case d = 2 and our proof's also show that the particular predicates we use in our PCPs are nonapproximable beyond the random assignment threshold.
Place, publisher, year, edition, pages
2005. Vol. 27, no 1, 46-75 p.
Computer Science Computational Mathematics
IdentifiersURN: urn:nbn:se:kth:diva-38021DOI: 10.1002/rsa.20050ISI: 000230469900003ScopusID: 2-s2.0-24144431561OAI: oai:DiVA.org:kth-38021DiVA: diva2:435916
QC 201108222011-08-222011-08-192011-08-22Bibliographically approved