N R, Aravind
(2015)
On the Expressive Power of ReadOnce Determinants.
In:
Fundamentals of Computation Theory [20th International Symposium, FCT 2015, Gdańsk, Poland, August 1719, 2015, Proceedings].
Lecture Notes in Computer Science, 9210
.
Springer International Publishing, Switzerland, pp. 95105.
ISBN 9783319221779
Full text not available from this repository.
(
Request a copy)
Abstract
We introduce and study the notion of readk projections of the determinant: a polynomial f∈F[x1,…,xn] is called a readk 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 readk projection of determinant if there is a readk projection of determinant f such that the monomial set of f is equal to S. We obtain basic results relating readk determinantal projections to the wellstudied 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 readonce projection of determinant, whereas mon(Permn) and mon(Sdn) are expressible as readonce projections of determinant. We also give examples of monomial sets which are not expressible as readonce projections of determinant.
[error in script]
Actions (login required)

View Item 