Name
Abstract | ||
|---|---|---|
A long line of work in Theoretical Computer Science shows that a function is close to a low-degree polynomial iff it is locally close to a low-degree polynomial. This is known as low-degree testing and is the core of the algebraic approach to construction of PCP. We obtain a low-degree test whose error, i.e., the probability it accepts a function that does not correspond to a low-degree polynomial, is polynomially smaller than existing low-degree tests. A key tool in our analysis is an analysis of the sampling properties of the incidence graph of degree-k curves and k′-tuples of points in a finite space \({\mathbb{F}^m}\). We show that the Sliding Scale Conjecture in PCP, namely the conjecture that there are PCP verifiers whose error is exponentially small in their randomness, would follow from a derandomization of our low-degree test. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00037-016-0149-4 | Computational Complexity |
Keywords | Field | DocType |
Low-degree testing, PCP, direct product, Sliding Scale Conjecture, 68Q17, 68Q25 | Discrete mathematics,Graph,Combinatorics,Direct product,Algebraic number,Polynomial,Sampling (statistics),Conjecture,Mathematics,Randomness,Exponential growth | Journal |
Volume | Issue | ISSN |
26 | 3 | 1420-8954 |
Citations | PageRank | References |
1 | 0.35 | 33 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dana Moshkovitz | 1 | 368 | 19.14 |