Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with #L:
TR96-024 | 21st March 1996
Eric Allender, Robert Beals, Mitsunori Ogihara

The complexity of matrix rank and feasible systems of linear equations

We characterize the complexity of some natural and important
problems in linear algebra. In particular, we identify natural
complexity classes for which the problems of (a) determining if a
system of linear equations is feasible and (b) computing the rank of
an integer matrix, ... 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 >>>

ISSN 1433-8092 | Imprint