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 >>>
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 >>>
We show that the complexity class LogFew is contained
in NL $\cap$ SPL. Previously, this was known only to
hold in the nonuniform setting.
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 >>>
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 >>>
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 >>>
