This month isn’t the most exciting for property testing. Just one paper to report (thanks to Clément for catching!), of which only a minor part is actually related to property testing.

**Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximation**, by Insu Han, Dmitry Malioutov, Haim Avron, and Jinwoo Shin (arXiv). The main results of the paper deal with approximating the trace of matrix functions. Consider symmetric matrix \(M \in \mathbb{R}^{d\times d}\), with eigenvalues \(\lambda_1, \lambda_2, \ldots, \lambda_d\). The paper gives new algorithms to approximate \(\sum_i f(\lambda_i)\). Each “operation” of the algorithm is a matrix-vector product, and the aim is to minimize the number of such operations. The property testing application is as follows. Suppose we wish to test if \(M\) is positive-definite (all \(\lambda_i > 0\)). We consider a matrix \(\epsilon\)-far from being positive-definite if the smallest eigenvalue is less than \(-\epsilon \|M\|_F = -\epsilon \sum_i \lambda^2_i\). The main theorems in this paper yield a testing algorithm (under this definition of distance) that makes \(o(d)\) matrix-vector products. While this is not exactly sublinear under a standard query access model, it is relevant when \(M\) is not explicitly represented and the only access is through such matrix-vector product queries.