ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-040 | 20th June 2002 00:00

Three-Query PCPs with Perfect Completeness over non-Boolean Domains

RSS-Feed

Abstract:

We study non-Boolean PCPs that have perfect completeness and read
three positions from 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 non-adaptive PCP with perfect completeness
and soundness d^{-1} + d^{-2} + epsilon, for any constant
epsilon > 0, and an adaptive PCP with perfect completeness and
soundness d^{-1} + epsilon, for any constant epsilon > 0.
These results match the best known constructions for the case d =
2 and our proofs also show that the particular predicates we use in
our PCPs are non-approximable beyond the random assignment threshold.



ISSN 1433-8092 | Imprint