Chou, ChiNing ;
Kumar, Mrinal ;
Solomon, Noam
Hardness vs Randomness for Bounded Depth Arithmetic Circuits
Abstract
In this paper, we study the question of hardnessrandomness 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^2n/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 subexponential time algorithm for polynomial identity testing of arithmetic circuits of depth Delta5.
This is incomparable to a beautiful result of Dvir et al.[SICOMP, 2009], where they showed that superpolynomial lower bounds for depth Delta circuits for any explicit family of polynomials (of potentially high degree) implies subexponential time deterministic PIT for depth Delta5 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) equiv 0, then, f can be computed by a circuit of size poly(n, s, r, d^{O(sqrt{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 nontrivial when t is small but d could be large, whereas our size upper bound is nontrivial when d is small, but t could be large.
BibTeX  Entry
@InProceedings{chou_et_al:LIPIcs:2018:8876,
author = {ChiNing Chou and Mrinal Kumar and Noam Solomon},
title = {{Hardness vs Randomness for Bounded Depth Arithmetic Circuits}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {13:113:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8876},
URN = {urn:nbn:de:0030drops88765},
doi = {10.4230/LIPIcs.CCC.2018.13},
annote = {Keywords: Algebraic Complexity, Polynomial Factorization Circuit Lower Bounds, Polynomial Identity Testing}
}
04.06.2018
Keywords: 

Algebraic Complexity, Polynomial Factorization Circuit Lower Bounds, Polynomial Identity Testing 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

04.06.2018 