Can I read The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-in on EtoBox?

The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-in by Mrinal Kumar; Shubhangi Saraf is a scholarly article available to read on EtoBox.

What is The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-in about?

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of depth reduction developed in the works of Agrawal and Vinay[1], Koiran [11] and Tavenas [16], and the use of the shifted partial derivative complexity measure developed in the works of Kayal [9] and Gupta et al [5]. These results inspired a flurry of other beautiful results and strong lower bounds for various classes of arithmetic circuits, in particular a recent work of Kayal et al [10] showing superpolynomial lower bounds for regular arithmetic formulas via an improved depth reduction for these formulas. It was left as an intriguing question if these methods could prove superpolynomial lower bounds for general (homogeneous) arithmetic formulas, and if so this would indeed be a breakthrough in arithmetic circuit complexity. 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 superpolynomial lower bounds for the class of homogeneous depth 4 circuits with top

Author

Mrinal Kumar; Shubhangi Saraf

Publisher

ACM

Published

2014

Language

EN