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