TY - GEN

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

AU - Moshkovitz, Dana

AU - Raz, Ran

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2006

Y1 - 2006

N2 - 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].

AB - 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].

KW - Locally Testable Codes

KW - Low degree testing

KW - Plane vs. Point test

KW - Probabilistically Checkable Proofs

UR - http://www.scopus.com/inward/record.url?scp=33748116316&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748116316&partnerID=8YFLogxK

U2 - 10.1145/1132516.1132520

DO - 10.1145/1132516.1132520

M3 - Conference contribution

AN - SCOPUS:33748116316

SN - 1595931341

SN - 9781595931344

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 21

EP - 30

BT - STOC'06

PB - Association for Computing Machinery (ACM)

T2 - 38th Annual ACM Symposium on Theory of Computing, STOC'06

Y2 - 21 May 2006 through 23 May 2006

ER -