Meena Mahajan, V. Vinay

We prove a new combinatorial characterization of the

determinant. The characterization yields a simple

combinatorial algorithm for computing the

determinant. Hitherto, all (known) algorithms for

determinant have been based on linear algebra. Our

combinatorial algorithm requires no division and works over

arbitrary commutative rings. It also lends itself to

more >>>

Stephen A. Fenner

We show that the counting classes AWPP and APP [Li 1993] are more robust

than previously thought. Our results identify asufficient condition for

a language to be low for PP, and we show that this condition is at least

as weak as other previously studied criteria. Our results imply that

more >>>

Michael Bauland, Elmar BĂ¶hler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

The parallel complexity class NC^1 has many equivalent models such as

polynomial size formulae and bounded width branching

programs. Caussinus et al. \cite{CMTV} considered arithmetizations of

two of these classes, #NC^1 and #BWBP. We further this study to

include arithmetization of other classes. In particular, we show that

counting paths ...
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 >>>

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan

We give a \#NC$^1$ upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$ hard. Our ... more >>>