ECCC-Report TR15-073https://eccc.weizmann.ac.il/report/2015/073Comments and Revisions published for TR15-073en-usSun, 26 Apr 2015 07:28:52 +0300
Paper TR15-073
| Lower Bounds for Sums of Products of Low arity Polynomials |
Neeraj Kayal,
Chandan Saha
https://eccc.weizmann.ac.il/report/2015/073We prove an exponential lower bound for expressing a polynomial as a sum of product of low arity polynomials. Specifically, we show that for the iterated matrix multiplication polynomial, $IMM_{d, n}$ (corresponding to the product of $d$ matrices of size $n \times n$ each), any expression of the form
$$ IMM_{d, n} = \sum_{i=1}^{s} \quad \prod_{j=1}^{m} \quad Q_{ij}, $$
where the $Q_{ij}$'s are of arity at most $t \leq \sqrt{d}$ (i.e. each $Q_{ij}$ depends on at most $t$ variables), the number of summands $s$ must be at least $d^{\Omega\left( \frac{d}{t} \right)}$.
A special case of this problem where the $Q_{ij}$'s are further restricted to have degree at most one was posed as an open problem by Shpilka and Wigderson [SW99] and recently resolved in [KS15]. We show that a refinement of the argument in [KS15] yields the above-mentioned lower bound on s, regardless of the degrees of the $Q_{ij}$'s (and also regardless of $m$, the number of factors in each summand). Lower bounds for the same model were also obtained in an almost simultaneous but independent work by Kumar and Saraf [KS15b].Sun, 26 Apr 2015 07:28:52 +0300https://eccc.weizmann.ac.il/report/2015/073