首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:The Chasm at Depth Four, and Tensor Rank : Old results, new insights
  • 本地全文:下载
  • 作者:Suryajith Chillara ; Mrinal Kumar ; Ramprasad Saptharishi
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2016
  • 卷号:2016
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 (1) d O log n log log n , constructing explicit tensors T : [ n ] d 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 (1) d n o (1) .

国家哲学社会科学文献中心版权所有