Thumbnail
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

   Open content in new tab
Source: ACM Digital Library