Thanh Minh Hoang, Thomas Thierauf

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 ...
more >>>

Thomas Thierauf, Thanh Minh Hoang

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.

Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

In this paper we study the complexity of Bounded Color

Multiplicity Graph Isomorphism (BCGI): the input is a pair of

vertex-colored graphs such that the number of vertices of a given

color in an input graph is bounded by $b$. We show that BCGI is in the

#L hierarchy ...
more >>>

Vikraman Arvind, T.C. Vijayaraghavan

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 >>>

T.C. Vijayaraghavan

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 >>>

T.C. Vijayaraghavan

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 >>>

T.C. Vijayaraghavan

Recently in [Vij09, Corollary 3.7] the complexity class ModL has been shown to be closed under complement assuming NL = UL. In this note we continue to show many other closure properties of ModL which include the following.

1. ModL is closed under $\leq ^L_m$ reduction, $\vee$(join) and $\leq ^{UL}_m$ ... more >>>