ECCC-Report TR15-181https://eccc.weizmann.ac.il/report/2015/181Comments and Revisions published for TR15-181en-usFri, 13 Nov 2015 09:14:05 +0200
Paper TR15-181
| On the size of homogeneous and of depth four formulas with low individual degree |
Neeraj Kayal,
Chandan Saha,
Sébastien Tavenas
https://eccc.weizmann.ac.il/report/2015/181Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ as 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 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.
Specifically, first define the formal degree of a node $\alpha$ with respect to a variable $x_i$ inductively as follows. For a leaf $\alpha$ it is $1$ if $\alpha$ is labelled with $x_i$ and zero otherwise; for an internal node $\alpha$ labelled with $\times$ (respectively $+$) it is the sum of (respectively the maximum of) the formal degrees of the children with respect to $x_i$. We call an arithmetic circuit as a multi-$r$-ic circuit if the formal degree of the output node with respect to any variable is at most $r$. We prove lower bounds for various subclasses of multi-$r$-ic circuits, including:
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 $ \left( \frac{n}{r^{1.1}} \right)^{\Omega \left(\sqrt{\frac{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.
Fri, 13 Nov 2015 09:14:05 +0200https://eccc.weizmann.ac.il/report/2015/181