Slightly Improved Lower Bounds for Homogeneous Multi-r-ic Formulas of Small-Depth

---

Link to the article

Authors

Suryajith Chillara

Publisher Information

• Journal: Information Processing Letters, vol 156

Abstract

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 \left(\mathrm{\Omega }\left(\frac{1}{r}{\left(\frac{n}{4}\right)}^{1/\mathrm{\Delta }}\right)\right)$ for all depths $\mathrm{\Delta }\le O\left(\frac{\log n}{\log r+\log \log n}\right)$. In this article we show an improved size lower bound of $\exp \left(\mathrm{\Omega }\left(\frac{\mathrm{\Delta }}{r}{\left(\frac{nr}{2}\right)}^{1/\mathrm{\Delta }}\right)\right)$ for all depths $\mathrm{\Delta }\le O\left(\frac{\log n}{\log r}\right)$, 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 $\mathrm{\Delta }$, and
2. for all $\mathrm{\Delta }\in [\omega (1),o\left(\frac{\log n}{\log r}\right)]$ 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 \emph{product decomposition} for bounded-depth multilinear formulas shown by Chillara, Limaye and Srinivasan (SIAM Journal of Computing, 2019).