### Tensor-Rank and Lower Bounds for Arithmetic FormulasTensor-Rank and Lower Bounds for Arithmetic Formulas

Access Restriction
Subscribed

 Author Raz, Ran Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Arithmetic circuits ♦ Homogenous circuits ♦ Lower bounds ♦ Multilinear circuits ♦ Tensor rank Abstract We show that any explicit example for a tensor $\textit{A}$ : $[n]^{r}$ → $\textit{F}$ with tensor-rank ≥ $n^{rċ(1™o(1))},$ where $\textit{r}$ = $\textit{r}(\textit{n})$ ≤ log $\textit{n}/log$ log $\textit{n}$ is super-constant, 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 multilinearization of arithmetic formulas, that gives the following results: We show that for any $\textit{n}-variate$ homogeneous polynomial $\textit{f}$ of degree $\textit{r},$ if there exists a (fanin-2) formula of size $\textit{s}$ and depth $\textit{d}$ for $\textit{f}$ then there exists a homogeneous formula of size $\textit{O}((\textit{d}+\textit{r}+1$ r) ċ $\textit{s})$ for $\textit{f}.$ In particular, for any $\textit{r}$ ≤ $\textit{O}(log$ $\textit{n}),$ if there exists a polynomial size formula for $\textit{f}$ then there exists a polynomial size homogeneous formula for $\textit{f}.$ This refutes a conjecture of Nisan and Wigderson [1996] and shows that super-polynomial lower bounds for homogeneous formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas. We show that for any $\textit{n}-variate$ set-multilinear polynomial $\textit{f}$ of degree $\textit{r},$ if there exists a (fanin-2) formula of size $\textit{s}$ and depth $\textit{d}$ for $\textit{f},$ then there exists a set-multilinear formula of size $\textit{O}((\textit{d}$ + $2)^{r}$ ċ $\textit{s})$ for $\textit{f}.$ In particular, for any $\textit{r}$ ≤ $\textit{O}(log$ $\textit{n}/log$ log $\textit{n}),$ if there exists a polynomial size formula for $\textit{f}$ then there exists a polynomial size set-multilinear formula for $\textit{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 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 6 Page Count 15 Starting Page 1 Ending Page 15

#### Open content in new tab

Source: ACM Digital Library