Name
Abstract | ||
|---|---|---|
The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial F(x1,...,xn) of degree at most s will evaluate to a nonzero value at some point on a grid Sn ⊆ Fn with |S| > s. Thus, there is a deterministic polynomial identity test (PIT) for all degree-s size-s algebraic circuits in n variables that runs in time poly(s) · (s + 1)n. In a surprising recent result, Agrawal, Ghosh and Saxena (STOC 2018) showed any deterministic blackbox PIT algorithm for degree-s, size-s, n-variate circuits with running time as bad as (Sn0.5−δ) HUGE(n), where δ > 0 and HUGE(n) is an arbitrary function, can be used to construct blackbox PIT algorithms for degree-s size s circuits with running time Sexp(exp(O(log* s))). Agrawal et al. asked if a similar conclusion followed if their hypothesis was weakened to having deterministic PIT with running time so(n) · HUGE(n). In this paper, we answer their question in the affirmative. We show that, given a deterministic black-box PIT that runs in time so(n) · HUGE(n) for all degree-s size-s algebraic circuits over n variables, we can obtain a deterministic blackbox PIT that runs in time Sexp(exp(O(log* s))) for all degree-s size-s algebraic circuits over n variables. In other words, any blackbox PIT with just a slightly non-trivial exponent of s compared to the trivial sO(n) test can be used to give a nearly polynomial time blackbox PIT algorithm.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.5555/3310435.3310475 | SODA '19: Symposium on Discrete Algorithms
San Diego
California
January, 2019 |
DocType | Volume | Citations |
Journal | abs/1807.06323 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |
| Ramprasad Saptharishi | 2 | 184 | 13.72 |
| Anamay Tengse | 3 | 0 | 0.34 |