Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree

摘要

Kayal, Saha and Tavenas (Theory of Computing, 2018), showed that any bounded-depth homogeneous formula of bounded individual degree (bounded by r) that computes an explicit polynomial over n variables must have size exp (Omega (1/r (n/4)(1/Delta))) for all depths Delta <= O (log n/log r+log log n). In this article we show an improved size lower bound of exp (Omega (Delta/r (nr/2)(1/Delta))) for all depths Delta <= O (log n/log r), and for the same explicit polynomial. In comparison to Kayal, Saha and Tavenas (Theory of Computing, 2018) (1) our results give superpolynomial lower bounds in a wider regime of depth Delta, and (2) for all Delta is an element of [omega(1), o (log n/log r)] our lower bound is asymptotically better.This improvement is due to a finer product decomposition of general homogeneous formulas of bounded-depth. This follows from an adaptation of a new product decomposition for bounded-depth multilinear formulas shown by Chillara, Limaye and Srinivasan (SIAM Journal of Computing, 2019). (C) 2019 Elsevier B.V. All rights reserved.