 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
[PDF (429K)]    [PS (2657K)]    [PS.GZ (515K)]
[Source ZIP]
Keywords: 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.

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. 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.
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).