Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Three-query PCPs with perfect completeness over non-Boolean domains
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
2005 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 27, no 1, 46-75 p.Article in journal (Refereed) Published
Abstract [en]

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) + epsilon, for any constant epsilon > 0, and an adaptive PCP with perfect cornpleteness and soundness d(-1) + epsilon, for any constant epsilon > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d(-1) + epsilon, for any constant epsilon > 0, where four positions are read from the proof. These results match the best known constructions for the case d = 2 and our proof's also show that the particular predicates we use in our PCPs are nonapproximable beyond the random assignment threshold.

Place, publisher, year, edition, pages
2005. Vol. 27, no 1, 46-75 p.
National Category
Computer Science Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-38021DOI: 10.1002/rsa.20050ISI: 000230469900003Scopus ID: 2-s2.0-24144431561OAI: oai:DiVA.org:kth-38021DiVA: diva2:435916
Note
QC 20110822Available from: 2011-08-22 Created: 2011-08-19 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Engebretsen, LarsHolmerin, Jonas
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Random structures & algorithms (Print)
Computer ScienceComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 33 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf