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