On the Expressive Power of Read-Once Determinants

N R, Aravind (2015) On the Expressive Power of Read-Once Determinants. In: Fundamentals of Computation Theory [20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings]. Lecture Notes in Computer Science, 9210 . Springer International Publishing, Switzerland, pp. 95-105. ISBN 978-3-319-22177-9

Full text not available from this repository. (Request a copy)

Abstract

We introduce and study the notion of read-k projections of the determinant: a polynomial f∈F[x1,…,xn] is called a read-k projection of determinant if f=det(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 Permn and the elementary symmetric polynomials of degree d on n variables Sdn for 2≤d≤n−2 are not expressible as read-once projection of determinant, whereas mon(Permn) and mon(Sdn) 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.

[error in script]

IITH Creators: