Lower Bounds for Sums of Products of Low arity Polynomials.
Neeraj Kayal, Chandan Saha · Electronic colloquium on computational complexity · 2015
We 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, IMMd,n (corresponding to the product of d matrices of size n × n each), any expression of the form IMMd,n = s ∑