Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with enumerative approximation:
TR02-016 | 30th January 2002
Alina Beygelzimer, Mitsunori Ogihara

On the Enumerability of the Determinant and the Rank

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

ISSN 1433-8092 | Imprint