Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size

Dana Moshkovitz, Ran Raz

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant 0 < α < 1, we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses random bits to make 7 queries to a proof of size, where each query is answered by bit long string, and the verifier has perfect completeness and error. The construction is by a new randomness-efficient version of the aggregation through curves technique. Its main ingredients are a recent low degree test with both sub-constant error and almost-linear size and a new method for constructing a short list of balanced curves.

Original languageEnglish (US)
Pages (from-to)367-422
Number of pages56
JournalComputational Complexity
Volume19
Issue number3
DOIs
StatePublished - Jan 1 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • Almost-linear size
  • Balanced curves
  • Probabilistically Checkable Proof (PCP)
  • Sub-constant error

Fingerprint Dive into the research topics of 'Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size'. Together they form a unique fingerprint.

  • Cite this