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

文章基本信息

  • 标题:Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials
  • 本地全文:下载
  • 作者:Christian Engels ; Raghavendra Rao B V ; Karteek Sreenivasaiah
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2016
  • 卷号:2016
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We study polynomials computed by depth five circuits, i.e., polynomials of the form t i =1 Q i where Q i = r i j =1 i j d i j , i j are linear forms and r i , t 0 . These circuits are a natural generalization of the well known class of circuits and received significant attention recently. We prove exponential lower bound for the monomial x 1 x n against the following sub-classes of circuits: \begin{itemize} \item Depth four homogeneous arithmetic circuits. \item Depth five [ n ] [ 21] and [ 2 n 1000 ] [ n ] arithmetic circuits where the bottom gate is homogeneous; \end{itemize} Our results show precisely how the fan-in of the middle gates, the degree of the bottom powering gates and the homogeneity at the bottom gates play a crucial role in the computational power of circuits.

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