Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR13-153 | 8th November 2013 03:38

#### The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in

TR13-153
Authors: Mrinal Kumar, Shubhangi Saraf
Publication: 8th November 2013 04:05
In this paper we study the power and limitations of depth reduction and shifted partial derivatives for arithmetic formulas. We do it via studying the class of depth 4 homogeneous arithmetic circuits. We show: (1) the first {\it superpolynomial lower bounds} for the class of homogeneous depth 4 circuits with top fan-in $o(\log n)$. The core of our result is to show {\it improved depth reduction} for these circuits. This class of circuits has received much attention for the problem of polynomial identity testing. We give the first nontrivial lower bounds for these circuits for any top fan-in $\geq 2$. (2) We show that improved depth reduction {\it is not possible} when the top fan-in is $\Omega(\log n)$. In particular this shows that the depth reduction procedure of Koiran and Tavenas [Koi12, Tav13] cannot be improved even for homogeneous formulas, thus strengthening the results of Fournier et al [FLMS13] who showed that depth reduction is tight for circuits, and answering some of the main open questions of [KSS13, FLMS13]. Our results in particular suggest that the method of depth reduction and shifted partial derivatives may not be powerful enough to prove superpolynomial lower bounds for (even homogeneous) arithmetic formulas.