ECCC-Report TR10-002https://eccc.weizmann.ac.il/report/2010/002Comments and Revisions published for TR10-002en-usMon, 04 Jan 2010 23:25:18 +0200
Paper TR10-002
| Tensor-Rank and Lower Bounds for Arithmetic Formulas |
Ran Raz
https://eccc.weizmann.ac.il/report/2010/002We 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.
Mon, 04 Jan 2010 23:25:18 +0200https://eccc.weizmann.ac.il/report/2010/002