@article{Allender1999,
    Abstract = {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 (as well as other problems) are complete under logspace reductions.{\textparagraph}As an important part of presenting this classification, we show that the ``exact counting logspace hierarchy'' collapses to near the bottom level. We review the definition of this hierarchy below. We further show that this class is closed under NC1-reducibility, and that it consists of exactly those languages that have logspace uniform span programs (introduced by Karchmer and Wigderson) over the rationals.{\textparagraph}In addition, we contrast the complexity of these problems with the complexity of determining if a system of linear equations has an integer solution.},
    Author = {Allender, E. and Beals, R. and Ogihara, M.},
    File = {31f52eb20cddd25fdf7a54d6e5b5c497794b (0) - a - a - j.pdf},
    ISSN = {1420-8954},
    Journal = {computational complexity},
    Month = {Nov},
    Number = {2},
    Pages = {99--126},
    Title = {The complexity of matrix rank and feasible systems of linear equations},
    URL = {https://doi.org/10.1007/s000370050023},
    Volume = {8},
    Year = {1999},
    bdsk-url-1 = {https://doi.org/10.1007/s000370050023},
    date-added = {2018-09-20 20:33:20 +0000},
    date-modified = {2018-09-20 20:33:20 +0000},
    day = {01},
    doi = {10.1007/s000370050023}
}

@article{Allender1999, Abstract = {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 (as well as other problems) are complete under logspace reductions.{\textparagraph}As an important part of presenting this classification, we show that the ``exact counting logspace hierarchy'' collapses to near the bottom level. We review the definition of this hierarchy below. We further show that this class is closed under NC1-reducibility, and that it consists of exactly those languages that have logspace uniform span programs (introduced by Karchmer and Wigderson) over the rationals.{\textparagraph}In addition, we contrast the complexity of these problems with the complexity of determining if a system of linear equations has an integer solution.}, Author = {Allender, E. and Beals, R. and Ogihara, M.}, File = {31f52eb20cddd25fdf7a54d6e5b5c497794b (0) - a - a - j.pdf}, ISSN = {1420-8954}, Journal = {computational complexity}, Month = {Nov}, Number = {2}, Pages = {99--126}, Title = {The complexity of matrix rank and feasible systems of linear equations}, URL = {https://doi.org/10.1007/s000370050023}, Volume = {8}, Year = {1999}, bdsk-url-1 = {https://doi.org/10.1007/s000370050023}, date-added = {2018-09-20 20:33:20 +0000}, date-modified = {2018-09-20 20:33:20 +0000}, day = {01}, doi = {10.1007/s000370050023} }