Three‐query PCPs with perfect completeness over non‐Boolean domains
Lars Fredrik Engebretsen, Jonas Holmerin · Random Structures and Algorithms · 2005
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 sizedfor some integer constantd≥ 2, we construct a nonadaptive PCP with perfect completeness and soundnessd−1+d−2+ ϵ, for any constant ϵ > 0, and an adaptive PCP with perfect completeness and soundnessd−1+ ϵ, for any constant ϵ > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundnessd−1+ ϵ, for any constant ϵ > 0, where four positions are read from the proof. These results match the best known constructions for the cased= 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