首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in
  • 本地全文:下载
  • 作者:Mrinal Kumar ; Shubhangi Saraf
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 {\it depth reduction} developed in the works of Agrawal-Vinay [AV08], Koiran [Koi12] and Tavenas [Tav13], and the use of the shifted partial derivative complexity measure developed in the works of Kayal [Kay12] and Gupta et al [GKKS13a]. 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 [KSS13] showing superpolynomial lower bounds for {\it regular} arithmetic formulas via an {\it 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 {\it superpolynomial lower bounds} for the class of homogeneous depth 4 circuits with top fan-in o(logn). 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 2. (2) We show that improved depth reduction {\it is not possible} when the top fan-in is (logn). 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.

  • 关键词:arithmetic circuits; Depth reduction; lower bounds; Shifted partial derivatives
国家哲学社会科学文献中心版权所有