Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > T.C. VIJAYARAGHAVAN:
All reports by Author T.C. Vijayaraghavan:

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


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

Characterization of ModL using Prime Modulus.

Revisions: 1

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


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


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


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




ISSN 1433-8092 | Imprint