Alina Beygelzimer, Mitsunori Ogihara

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

more >>>