TR15-181 Authors: Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Publication: 13th November 2015 09:14

Downloads: 1389

Keywords:

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}]$ 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.