Testing Matrix Rank, Optimally

Maria-Florina Balcan, Yi Li, David P. Woodruff +1

We show that for the problem of testing if a matrix $A\in F^{n\times n}$ has rank at most $d$, or requires changing an $\epsilon$-fraction of entries to have rank at most $d$, there is…