Testing Matrix Rank, Optimally
  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 a non-adaptive query algorithm making
$\widetilde{O}(d^2/\epsilon)$ queries. Our algorithm works for any field $F$.
This improves upon the previous $O(d^2/\epsilon^2)$ bound (SODA'03), and
bypasses an $\Omega(d^2/\epsilon^2)$ lower bound of (KDD'14) which holds if the
algorithm is required to read a submatrix. Our algorithm is the first such
algorithm which does not read a submatrix, and instead reads a carefully
selected non-adaptive pattern of entries in rows and columns of $A$. We
complement our algorithm with a matching query complexity lower bound for
non-adaptive testers over any field. We also give tight bounds of
$\widetilde{\Theta}(d^2)$ queries in the sensing model for which query access
comes in the form of $\langle X_i, A\rangle:=tr(X_i^\top A)$; perhaps
surprisingly these bounds do not depend on $\epsilon$.
  We next develop a novel property testing framework for testing numerical
properties of a real-valued matrix $A$ more generally, which includes the
stable rank, Schatten-$p$ norms, and SVD entropy. Specifically, we propose a
bounded entry model, where $A$ is required to have entries bounded by $1$ in
absolute value. We give upper and lower bounds for a wide range of problems in
this model, and discuss connections to the sensing model above.
