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

文章基本信息

  • 标题:An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
  • 本地全文:下载
  • 作者:Neeraj Kayal ; Nutan Limaye ; Chandan Saha
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show here a 2(dlogN) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N=d3 in our case) with 01 -coefficients such that for any representation of a polynomial f in this family of the form f=ijQij where the Qij's are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that the total number of monomials in all the Qij's put together must be at least 2(dlogN) .

    The abovementioned family which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. For polynomial families in VP we show the following: Any homogeneous depth four arithmetic formula computing the Iterated Matrix Multiplication polynomial IMMnd --- the (11) -th entry of the product of d generic nn matrices --- has size n(logn), if d=(log2n). Moreover, any homogeneous depth four formula computing the determinant polynomial Detn --- the determinant of a generic nn matrix --- has size n(logn). Our work builds on the recent lower bound results and yields an improved quantitative bound as compared to the recent indepedent work by Kumar and Saraf (ECCC TR13-181).

  • 关键词:arithmetic formulas; Depth Four; Homogeneous Circuit; lower bound; Shifted partial derivatives
国家哲学社会科学文献中心版权所有