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



REPORTS > KEYWORD > NON-BOOLEAN DOMAINS.:
Reports tagged with Non-Boolean Domains.:
TR02-040 | 20th June 2002
Lars Engebretsen, Jonas Holmerin

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

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} ... more >>>



ISSN 1433-8092 | Imprint