TR02-016 Authors: Alina Beygelzimer, Mitsunori Ogihara

Publication: 27th February 2002 17:43

Downloads: 3293

Keywords:

We investigate the complexity of enumerative approximation of

two elementary problems in linear algebra, computing the rank

and the determinant of a matrix. In particular, we show that

if there exists an enumerator that, given a matrix, outputs a

list of constantly many numbers, one of which is guaranteed to

be the rank of the matrix, then it can be determined in $\AC^0$

(with oracle access to the enumerator) which of these numbers

is the rank. Thus, for example, if the enumerator is an FL

function, then the problem of computing the rank is in FL.

The result holds for matrices over any commutative ring whose

size grows at most polynomially with the size of the matrix.

The existence of such an enumerator also implies a slightly

stronger collapse of the exact counting logspace hierarchy.

For the determinant function DET we establish the following

two results:

1. If DET is poly-enumerable in logspace, then DET is in FL.

2. For any prime $p$, if DET modulo $p$ is $(p-1)$-enumerable in

Mod_pL, then DET modulo $p$ is in FL.