Name
Abstract | ||
|---|---|---|
Given (the table of) 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 ane 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 the 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 check- able proofs (PCPs). The error of the low degree tester is related to the error of the PCP |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/060656838 | SIAM Journal on Computing |
Keywords | Field | DocType |
sampling | Affine transformation,Discrete mathematics,Finite field,Combinatorics,Polynomial,Degree of a polynomial,Oracle,Linear subspace,Probabilistic logic,Soundness,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 1 | 0097-5397 |
Citations | PageRank | References |
17 | 0.77 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dana Moshkovitz | 1 | 368 | 19.14 |
| Ran Raz | 2 | 2772 | 180.87 |