Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Logspace counting classes:
TR01-028 | 16th March 2001
Thanh Minh Hoang, Thomas Thierauf

The Complexity of the Minimal Polynomial

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

TR04-024 | 26th March 2004
Thomas Thierauf, Thanh Minh Hoang

On Closure Properties of GapL

Revisions: 1 , Comments: 1

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

TR04-121 | 7th December 2004
Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

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

TR08-052 | 29th April 2008
Vikraman Arvind, T.C. Vijayaraghavan

The Orbit problem is in the GapL Hierarchy

Revisions: 1

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

TR09-009 | 18th December 2008
T.C. Vijayaraghavan

Checking Equality of Matroid Linear Representations and the Cycle Matching Problem

Revisions: 2

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

TR09-082 | 20th September 2009
T.C. Vijayaraghavan

Characterization of ModL using Prime Modulus.

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

TR10-099 | 20th June 2010
T.C. Vijayaraghavan

A Note on Closure Properties of ModL

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

ISSN 1433-8092 | Imprint