Volume 14 (2018)
Article 16 pp. 1-46

On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree

Received: August 18, 2016

Revised: November 24, 2017

Published: December 6, 2018

Revised: November 24, 2017

Published: December 6, 2018

**Keywords:**complexity theory, lower bounds, algebraic complexity, arithmetic formulas, arithmetic circuits, partial derivatives

**Categories:**complexity theory, lower bounds, algebraic complexity, arithmetic formulas, arithmetic circuits, partial derivatives

**ACM Classification:**F.1.3, F.1.1

**AMS Classification:**68Q17, 68Q15

**Abstract:**
[Plain Text Version]

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.

- An $N^{\Omega(\log N)}$ lower bound against
*homogeneous*multi-$r$-ic formulas (for an explicit multi-$r$-ic polynomial on $N$ variables). - A $({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. - 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).