Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR13-091 | 17th June 2013 15:14

A super-polynomial lower bound for regular arithmetic formulas.

TR13-091
Authors: Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
Publication: 18th June 2013 19:21
We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree of its output polynomial, we refer to as a regular formula. As usual, we allow arbitrary constants from the underlying field $\mathbb{F}$ on the incoming edges to a $+$ gate so that a $+$ gate can in fact compute an arbitrary $\mathbb{F}$-linear combination of its inputs. We show that there is an $(n^2+1)$-variate polynomial of degree $2n$ in VNP such that any regular formula computing it must be of size at least $n^{\Omega(\log n)}$.
Along the way, we examine depth four ($\Sigma \Pi \Sigma \Pi$) regular formulas wherein all multiplication gates in the layer adjacent to the inputs have fanin $a$ and all multiplication gates in the layer adjacent to the output node have fanin $b$. We refer to such formulas as $\Sigma \Pi^{[b]} \Sigma \Pi^{[a]}$-formulas. We show that there exists an $n^2$-variate polynomial of degree $n$ in VNP such that any $\Sigma \Pi^{[O(\sqrt{n})]} \Sigma\Pi^{[\sqrt{n}]}$-formula computing it must have top fan-in at least $2^{\Omega(\sqrt{n}\cdot \log n)}$. In comparison, Tavenas (MFCS 2013) has recently shown that every $n^{O(1)}$-variate polynomial of degree $n$ in VP admits a $\Sigma \Pi^{[O(\sqrt{n})]} \Sigma\Pi^{[\sqrt{n}]}$-formula of top fan-in $2^{O(\sqrt{n} \cdot \log n)}$. This means that any further asymptotic improvement either in our lower bound for such formulas (to say $2^{\omega(\sqrt{n} \log n)}$) or in Tavenas' upper bound (to say $2^{o(\sqrt{n} \log n)}$ ) will imply that VP is different from VNP.