We investigate the computational complexity of the minimal polynomial of an integer matrix. We show that the computation of the minimal polynomial is in AC^0(GapL), the AC^0-closure of the logspace counting class GapL, which is contained in NC^2. Our main result is that the problem is hard for GapL (under ... more >>>

We show necessary and sufficient conditions that certain algebraic functions like the rank or the signature of an integer matrix can be computed in GapL. more >>>

The \emph{Orbit problem} is defined as follows: Given a matrix $A\in \Q ^{n\times n}$ and vectors $\x,\y\in \Q ^n$, does there exist a non-negative integer $i$ such that $A^i\x=\y$. This problem was shown to be in deterministic polynomial time by Kannan and Lipton in \cite{KL1986}. In this paper we place ... more >>>

Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for $\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given ... more >>>

The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in Definition 1.4.1, Vij08],[Definition 3.1, AV]). In this paper, under the assumption that NL =UL, we show that for every language $L\in ModL$ there exists a function $f\in \sharpL$ and a function $g\in FL$ such that ... more >>>