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

文章基本信息

  • 标题:On the expressive power of read-once determinants
  • 本地全文:下载
  • 作者:Pushkar Joglekar ; Aravind N.R.
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We introduce and study the notion of read- k projections of the determinant: a polynomial f F [ x 1 x n ] is called a {\it read- k projection of determinant} if f = d et ( M ) , where entries of matrix M are either field elements or variables such that each variable appears at most k times in M . A monomial set S is said to be expressible as read- k projection of determinant if there is a read- k projection of determinant f such that the monomial set of f is equal to S . We obtain basic results relating read- k determinantal projections to the well-studied notion of determinantal complexity. We show that for sufficiently large n , the n n permanent polynomial Per m n and the elementary symmetric polynomials of degree d on n variables S n d for 2 d n − 2 are not expressible as read-once projection of determinant, whereas mon ( Per m n ) and mon ( S n d ) are expressible as read-once projections of determinant. We also give examples of monomial sets which are not expressible as read-once projections of determinant.

  • 关键词:determinant ; determinantal complexity ; permanent ; read-once
国家哲学社会科学文献中心版权所有