Sub-constant error low degree test of almost-linear size

Dana Moshkovitz, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

Given a function f: Fm → F over a finite field F, a low degree tester tests its agreement with an m-variate polynomial of total degree at most d over F. The tester is usually given access to an oracle A providing the supposed restrictions of f to affine subspaces of constant dimension (e.g., lines, planes, etc.). The tester makes very few (probabilistic) queries to f and to A (say, one query to f and one query to A), and decides whether to accept or reject based on the replies. We wish to minimize two parameters of a tester: its error and its size. The error bounds the probability that the tester accepts although the function is far from a low degree polynomial. The size is the number of bits required to write the oracle replies on all possible tester's queries. Low degree testing is a central ingredient in most constructions of probabilistically checkable proofs (PCPs) and locally testable codes (LTCs). The error of the low degree tester is related to the soundness of the PCP and its size is related to the size of the PCP (or the length of the LTC). We design and analyze new low degree testers that have both sub-constant error o(1) and almost-linear size n1+o(1) (where n = |F|m). Previous constructions of sub-constant error testers had polynomial size [3, 16]. These testers enabled the construction of PCPs with sub-constant soundness, but polynomial size [3, 16, 9]. Previous constructions of almost-linear size testers obtained only constant error [13, 7]. These testers were used to construct almost-linear size LTCs and almost-linear size PCPs with constant soundness [13, 7, 5, 6, 8].

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery (ACM)
Pages21-30
Number of pages10
ISBN (Print)1595931341, 9781595931344
DOIs
StatePublished - 2006
Externally publishedYes
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Other

Other38th Annual ACM Symposium on Theory of Computing, STOC'06
CountryUnited States
CitySeattle, WA
Period5/21/065/23/06

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Locally Testable Codes
  • Low degree testing
  • Plane vs. Point test
  • Probabilistically Checkable Proofs

Fingerprint Dive into the research topics of 'Sub-constant error low degree test of almost-linear size'. Together they form a unique fingerprint.

  • Cite this

    Moshkovitz, D., & Raz, R. (2006). Sub-constant error low degree test of almost-linear size. In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (pp. 21-30). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1132516.1132520