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

Eric Allender, Klaus Reinhardt

We show that the perfect matching problem is in the

complexity class SPL (in the nonuniform setting).

This provides a better upper bound on the complexity of the

matching problem, as well as providing motivation for studying

the complexity class SPL.

Using similar ...
more >>>

Eric Allender, Shiyu Zhou

We show that the complexity class LogFew is contained

in NL $\cap$ SPL. Previously, this was known only to

hold in the nonuniform setting.

Eric Allender, Vikraman Arvind, Meena Mahajan

The aim of this paper is to use formal power series techniques to

study the structure of small arithmetic complexity classes such as

GapNC^1 and GapL. More precisely, we apply the Kleene closure of

languages and the formal power series operations of inversion and

root ...
more >>>

Meena Mahajan, P R Subramanya, V Vinay

The Pfaffian of an oriented graph is closely linked to

Perfect Matching. It is also naturally related to the determinant of

an appropriately defined matrix. This relation between Pfaffian and

determinant is usually exploited to give a fast algorithm for

computing Pfaffians.

We present the first completely combinatorial algorithm for ... more >>>

Meena Mahajan, V Vinay

In this note, we consider the problem of computing the

coefficients of the characteristic polynomial of a given

matrix, and the related problem of verifying the

coefficents.

Santha and Tan [CC98] show that verifying the determinant

(the constant term in the characteristic polynomial) is

complete for the class C=L, ...
more >>>