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

文章基本信息

  • 标题:Nonnegative rank measures and monotone algebraic branching programs
  • 本地全文:下载
  • 作者:Hervé Fournier ; Guillaume Malod ; Maud Szusterman
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-19
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove a rather tight lower bound for the computation of elementary symmetric polynomials by algebraic branching programs in the monotone setting or, equivalently, in the homogeneous syntactically multilinear setting.

  • 关键词:elementary symmetric polynomials ; lower bounds
国家哲学社会科学文献中心版权所有