## On Computing Multilinear Polynomials using Multi-$r$-ic Depth Four Circuits

### Authors

Suryajith Chillara

### Publisher Information

- Journal: ACM Transactions on Computation Theory, Vol. 13, Issue 3, Article 16, Pages 1-21
- Conference: STACS 2020, Pages 47:1-47-16 (LIPIcs, Vol. 154)

## Abstract

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which the polynomial computed at every node has a bound on the individual degree of $r \geq 1$ with respect to all its variables (referred to as multi-$r$-c circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better bounds as the value of $r$ increases.

Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree $r$ computing an explicit multilinear polynomial on $n^{O(1)}$ variables and degree $d$, must have size at least $\left(\frac{n}{r^{1.1}}\right)^{\Omega\left(\sqrt{\frac{d}{r}}\right)}$. This bound however deteriorates as the value of $r$ increases. It is a natural question to ask if we can prove a bound that does not deteriorate as the value of $r$ increases, or a bound that holds for a *larger* regime of $r$.

In this paper, we prove a lower bound which does not deteriorate with increasing values of $r$, albeit for a specific instance of $d = d(n)$ but for a *wider* range of $r$. Formally, for all large enough integers $n$ and a small constant $\eta$, we show that there exists an explicit polynomial on $n^{O(1)}$ variables and degree $\Theta(\log^2 n)$ such that any depth four circuit of bounded individual degree $r\leq n^{\eta}$ must have size at least $\exp\left(\Omega\left(\log^2 n\right)\right)$. This *improvement* is obtained by suitably adapting the complexity measure of Kayal et al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et al. (SIAM J. Computing, 2017).