Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR16-096 | 1st August 2017 06:05

#### The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revision #2
Authors: Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay
Accepted on: 1st August 2017 06:05
Keywords:

Abstract:

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this chain of results. We then abstract the main ingredient to apply it to formulas and constant depth circuits, and show more structured depth reductions for them.

In an apriori surprising result, Raz [Raz10] showed that for any $n$ and $d$, such that
$\omega(1) \leq d \leq O\left(\frac{\log n}{\log\log n}\right)$, constructing explicit tensors $T:[n]^d \rightarrow F$ of high enough rank would imply superpolynomial lower bounds for arithmetic formulas over the field $\F$. Using the additional structure we obtain from our proof of the depth reduction for arithmetic formulas, we give a new and arguably simpler proof of this connection. We also extend this result for homogeneous formulas to show that, in fact, the connection holds for any $d$ such that $\omega(1) \leq d \leq n^{o(1)}$.

Changes to previous version:

Correction - tensor rank is sub-multiplicative.Earlier version incorrectly mentioned that it is multiplicative.

Revision #1 to TR16-096 | 14th June 2016 15:24

#### The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revision #1
Authors: Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay
Accepted on: 14th June 2016 15:24
Keywords:

Abstract:

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Koiran [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this chain of results. We then abstract the main ingredient to apply it to formulas and constant depth circuits, and show more structured depth reductions for them.

In an apriori surprising result, Raz [Raz10] showed that for any $n$ and $d$, such that
$\omega(1) \leq d \leq O\left(\frac{\log n}{\log\log n}\right)$, constructing explicit tensors $T:[n]^d \rightarrow F$ of high enough rank would imply superpolynomial lower bounds for arithmetic formulas over the field $\F$. Using the additional structure we obtain from our proof of the depth reduction for arithmetic formulas, we give a new and arguably simpler proof of this connection. We also extend this result for homogeneous formulas to show that, in fact, the connection holds for any $d$ such that $\omega(1) \leq d \leq n^{o(1)}$.

Changes to previous version:

Corrected some typos

### Paper:

TR16-096 | 14th June 2016 05:36

#### The Chasm at Depth Four, and Tensor Rank : Old results, new insights

TR16-096
Authors: Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay
Publication: 14th June 2016 12:31
In an apriori surprising result, Raz [Raz10] showed that for any $n$ and $d$, such that
$\omega(1) \leq d \leq O\left(\frac{\log n}{\log\log n}\right)$, constructing explicit tensors $T:[n]^d \rightarrow F$ of high enough rank would imply superpolynomial lower bounds for arithmetic formulas over the field $\F$. Using the additional structure we obtain from our proof of the depth reduction for arithmetic formulas, we give a new and arguably simpler proof of this connection. We also extend this result for homogeneous formulas to show that, in fact, the connection holds for any $d$ such that $\omega(1) \leq d \leq n^{o(1)}$.