| Abstract: | 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 + ?, for any constant ? > 0, and an adaptive PCP with perfect completeness and soundness d?1 + ?, for any constant ? > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d?1 + ?, for any constant ? > 0, where four positions are read from the proof. 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 nonapproximable beyond the random assignment threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 |
