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.