Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-002 | 4th January 2010 23:25

Tensor-Rank and Lower Bounds for Arithmetic Formulas

RSS-Feed




TR10-002
Authors: Ran Raz
Publication: 4th January 2010 23:25
Downloads: 1542
Keywords: 


Abstract:

We show that any explicit example for a tensor $A:[n]^r \rightarrow \mathbb{F}$ with tensor-rank
$\geq n^{r \cdot (1- o(1))}$,
(where $r = r(n) \leq \log n / \log \log n$), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over $\mathbb{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 multilinearization 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 \left( {d+r+1 \choose r} \cdot s \right)$ for $f$. In particular, for any $r \leq \log n / \log \log n$, 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 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 \left( (d+2)^r \cdot s \right)$ for $f$.
In particular, for any $r \leq \log n / \log \log n$, 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.



ISSN 1433-8092 | Imprint