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

文章基本信息

  • 标题:Lower bounds for the circuit size of partially homogeneous polynomials
  • 本地全文:下载
  • 作者:Hong Van Le
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this paper we associate to each multivariate polynomial f that is homogeneous relative to a subset of its variables a series of polynomial families P ( f ) of m -tuples of homogeneous polynomials of equal degree such that the circuit size of any member in P ( f ) is bounded from above by the circuit size of f . This provides a method for obtaining lower bounds for the circuit size of f by proving ( s r ) -(weak) elusiveness of the polynomial mapping associated with P ( f ) . We discuss some algebraic methods for proving the ( s r ) -(weak) elusiveness. We also improve estimates in the normal homogeneous-form of an arithmetic circuit obtained by Raz in \cite{Raz2009} which results in better lower bounds for circuit size (Lemma \ref{lem:cor38}, Remark \ref{rem:cor38}). Our methods yield non-trivial lower bound for the circuit size of several classes of multivariate homogeneous polynomials (Corollary \ref{cor:412}, Example \ref{ex:bi}). }

  • 关键词:lower bound for circuit size
国家哲学社会科学文献中心版权所有