中央研究院 資訊科學研究所

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 ∆arithmetic circuits of size poly(n), then there is a deterministic sub-exponential time algorithm for polynomial identity testing of arithmetic circuits of depth ∆ −5. This is incomparable to a beautiful result of Dvir et al.[SICOMP, 2009], where they showed that super-polynomial lower bounds for depth ∆circuits for any explicit family of polynomials (of potentially high degree) implies sub-exponential time deterministic PIT for depth ∆ −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 ∆and P(x_1,x_2,…,x_n,f) ≡0, then, f can be computed by a circuit of size poly(n, s, r, d^{O([@BackSlash]sqrt{d})}) and depth ∆+ 3. In comparison, Dvir et al. showed that f can be computed by a circuit of depth ∆+ 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.

This is a joint work with Mrinal Kumar and Noam Solomon.

Chi-Ning Chou is a Ph.D. student at Harvard University advised by Professor Boaz Barak. He received his B.S. in computer science from National Taiwan University in 2016. He has various research interest in theoretical computer science including computational complexity, algebraic computation, hardness of approximation etc.