On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
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 …