Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR05-086 | 9th October 2005 00:00

Sub-Constant Error Low Degree Test of Almost Linear Size

RSS-Feed




Revision #1
Authors: Dana Moshkovitz, Ran Raz
Accepted on: 9th October 2005 00:00
Downloads: 1349
Keywords: 


Abstract:

Given a function f:F^m rightarrow F over a finite field F, a low degree tester tests its proximity to 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 n^{1+o(1)} (where n=|F|^m). Previous constructions of sub-constant error testers had polynomial size. These testers enabled the construction of PCPs with sub-constant soundness, but polynomial size. Previous constructions of almost-linear size testers obtained only constant error. These testers were used to construct almost-linear size LTCs and almost-linear size PCPs with constant soundness.


Paper:

TR05-086 | 14th August 2005 00:00

Sub-Constant Error Low Degree Test of Almost Linear Size





TR05-086
Authors: Dana Moshkovitz, Ran Raz
Publication: 14th August 2005 18:44
Downloads: 1279
Keywords: 


Abstract:

Given a function f:F^m \rightarrow F over a finite
field F, a low degree tester tests its proximity to
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
n^{1+o(1)} (where n=|F|^m). Previous
constructions of sub-constant error testers had
polynomial size. These testers enabled the
construction of PCPs with sub-constant soundness, but
polynomial size. Previous
constructions of almost-linear size testers obtained only
constant error. These testers were used to
construct almost-linear size LTCs and almost-linear
size PCPs with constant soundness.



ISSN 1433-8092 | Imprint