Estimating the rank of a large sparse matrix
There is a very neat randomized algorithm by Cheung, Kwok, and Lau, which computes the rank of an $n\times m$ matrix $A$, $n\le m$, in time $O(\mathrm{nnz}(A) + \min\{n^\omega, n\cdot\mathrm{nnz}(A)\})$. Here $\mathrm{nnz}(A)$ is the number of nonzero elements of $A$, and $\omega$ is the matrix multiplication exponent. Not quite what you are asking for, but it does improve on fast matrix multiplication based methods for $\mathrm{nnz}(A) = o(n^{\omega - 1})$.