Theory of Computing ------------------- Title : On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree Authors : Neeraj Kayal, Chandan Saha, and Sebastien Tavenas Volume : 14 Number : 16 Pages : 1-46 URL : https://theoryofcomputing.org/articles/v014a016 Abstract -------- Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ a multi-$r$-ic polynomial if the degree of $f$ with respect to any variable is at most $r$. (This generalizes the notion of multilinear polynomials.) We investigate the arithmetic circuits in which the output is syntactically forced to be a multi-$r$-ic polynomial and refer to these as multi-$r$-ic circuits. We prove lower bounds for several subclasses of such circuits, including the following. 1. An $N^{\Omega(\log N)}$ lower bound against _homogeneous_ multi-$r$-ic formulas (for an explicit multi-$r$-ic polynomial on $N$ variables). 2. An $({n}/{r^{1.1}})^{\Omega \left(\sqrt{{d}/{r}} \right)} $ lower bound against _depth-four_ multi-$r$-ic circuits computing the polynomial $\mathrm{IMM}_{n, d}$ corresponding to the product of $d$ matrices of size $n \times n$ each. 3. A $2^{\Omega \left( \sqrt{N} \right)} $ lower bound against depth-four multi-$r$-ic circuits computing an explicit multi-$r$-ic polynomial on $N$ variables. A conference version of this paper appeared in the Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC'16).