Tensor-Rank and Lower Bounds for Arithmetic Formulas

We show that any explicit example for a tensor A : (n)r ! F with tensor-rank nr (1 o(1)), (where r = r(n) logn= log logn), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over F. This shows that strong enough lower bounds for the size of arithmetic formulas of depth 3 imply super- polynomial lower bounds for the size of general arithmetic formulas. One component of our proof is a new approach for homogenization and multilin- earization of arithmetic formulas, that gives the following results: We show that for any n-variate homogenous polynomial f of degree r, if there exists a (fanin-2) formula of size s and depth d for f then there exists a homogenous formula of size O d+r+1 r s for f. In particular, for any r logn, if there exists a polynomial size formula for f then there exists a polynomial size homogenous formula for f. This refutes a conjecture of Nisan and Wigderson (NW95) and shows that super- polynomial lower bounds for homogenous formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas. We show that for any n-variate set-multilinear polynomial f of degree r, if there exists a (fanin-2) formula of size s and depth d for f then there exists a set-multilinear formula of size O ((d + 2)r s) for f. In particular, for any r logn= log logn, if there exists a polynomial size formula for f then there exists a polynomial size set-multilinear formula for f. This shows that super-polynomial lower bounds for set-multilinear formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas.