Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with gapl:
TR97-036 | 1st August 1997
Meena Mahajan, V Vinay

Determinant: Combinatorics, Algorithms, and Complexity

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

TR98-019 | 5th April 1998
Eric Allender, Klaus Reinhardt

Isolation, Matching, and Counting

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

TR98-023 | 16th April 1998
Eric Allender, Shiyu Zhou

Uniform Inclusions in Nondeterministic Logspace

We show that the complexity class LogFew is contained
in NL $\cap$ SPL. Previously, this was known only to
hold in the nonuniform setting.

more >>>

TR99-008 | 19th March 1999
Eric Allender, Vikraman Arvind, Meena Mahajan

Arithmetic Complexity, Kleene Closure, and Formal Power Series

Revisions: 1 , Comments: 1

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

TR99-030 | 9th July 1999
Meena Mahajan, P R Subramanya, V Vinay

A Combinatorial Algorithm for Pfaffians

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

TR00-088 | 28th November 2000
Meena Mahajan, V Vinay

A note on the hardness of the characteristic polynomial

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

Santha and Tan [CC98] show that verifying the determinant
(the constant term in the characteristic polynomial) is
complete for the class C=L, ... more >>>

ISSN 1433-8092 | Imprint