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

文章基本信息

  • 标题:On Lower Bounds for Constant Width Arithmetic Circuits
  • 本地全文:下载
  • 作者:Vikraman Arvind ; Pushkar Joglekar ; Srikanth Srinivasan
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit of width k. It follows, from the definition of the polynomial, that the constant-width and the constant-depth hierarchies of monotone arithmetic circuits are infinite, both in the commutative and the noncommutative settings.2. We prove hardness-randomness tradeoffs for identity testing constant-width commutative circuits analogous to [KI03,DSY08].

  • 关键词:Constant width; lower bounds; Monotone Arithmetic Circuits
国家哲学社会科学文献中心版权所有