Premium
Three‐query PCPs with perfect completeness over non‐Boolean domains
Author(s) -
Engebretsen Lars,
Holmerin Jonas
Publication year - 2005
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20050
Subject(s) - soundness , completeness (order theory) , mathematical proof , constant (computer programming) , discrete mathematics , mathematics , computer science , combinatorics , programming language , geometry , mathematical analysis
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