Name
Abstract | ||
|---|---|---|
In this paper, we study the question of hardness-randomness tradeoffs for bounded depth arithmetic circuits. We show that if there is a family of explicit polynomials {f(n)}, where f(n) is of degree O(log(2) n/log(2) log n) in n variables such that f(n) cannot be computed by a depth Delta arithmetic circuits of size poly(n), then there is a deterministic sub-exponential time algorithm for polynomial identity testing of arithmetic circuits of depth Delta - 5. This is incomparable to a beautiful result of Dvir et al.[SICOMP, 2009], where they showed that super-polynomial lower bounds for depth Delta circuits for any explicit family of polynomials (of potentially high degree) implies sub-exponential time deterministic PIT for depth Delta - 5 circuits of bounded individual degree. Thus, we remove the "bounded individual degree" condition in the work of Dvir et al. at the cost of strengthening the hardness assumption to hold for polynomials of low degree. The key technical ingredient of our proof is the following property of roots of polynomials computable by a bounded depth arithmetic circuit : if f(x(1), x(2), . . . , x(n)) and P(x(1), x(2), . . . , x(n), y) are polynomials of degree d and r respectively, such that P can be computed by a circuit of size s and depth Delta and P(x(1), x(2), . . . , x(n), f) equivalent to 0, then, f can be computed by a circuit of size poly(n, s, r, d(O(root d))) and depth Delta + 3. In comparison, Dvir et al. showed that f can be computed by a circuit of depth Delta + 3 and size poly(n, s, r, d(t)), where t is the degree of P in y. Thus, the size upper bound in the work of Dvir et al. is non-trivial when t is small but d could be large, whereas our size upper bound is non-trivial when d is small, but t could be large. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.CCC.2018.13 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
Algebraic Complexity,Polynomial Factorization Circuit Lower Bounds,Polynomial Identity Testing | Arithmetic circuits,Polynomial identity testing,Discrete mathematics,Polynomial,Computer science,Upper and lower bounds,Electronic circuit,Algebraic complexity,Randomness,Bounded function | Conference |
Volume | ISSN | Citations |
102 | 1868-8969 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chi-Ning Chou | 1 | 3 | 4.83 |
| Mrinal Kumar 0001 | 2 | 64 | 9.94 |
| Noam Solomon | 3 | 8 | 8.17 |