Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-141 | 26th August 2015 15:57

On the expressive power of read-once determinants


Authors: Pushkar Joglekar, Aravind N.R.
Publication: 26th August 2015 23:02
Downloads: 700


We introduce and study the notion of read-$k$ projections of the determinant: a polynomial $f \in \mathbb{F}[x_1, \ldots, x_n]$ is called a {\it 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 \times n$ permanent polynomial $Perm_n$ and the elementary symmetric polynomials of degree $d$ on $n$ variables $S_n^d$ for $2 \leq d \leq n-2$ are not expressible as read-once projection of determinant, whereas $mon(Perm_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.

ISSN 1433-8092 | Imprint