As October draws to a close, we are left with four new papers this month.

Testing Matrix Rank, Optimally, by Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang (arXiv). This work investigates the problem of non-adaptively testing matrix properties, in both the standard query model and the more general sensing model, in which the algorithm may query the component-wise inner product of the matrix with “sensing” matrices. It proves tight upper and lower bounds of \(\tilde \Theta(d^2/\varepsilon)\) for the query model, and eliminating the dependence on \(\varepsilon\) in the sensing model. Furthermore, they introduce a bounded entry model for testing of matrices, in which the entries have absolute value bounded by 1, in which they prove various bounds for testing stable rank, Schatten-\(p\) norms, and SVD entropy.

Testing Halfspaces over Rotation-Invariant Distributions, by Nathaniel Harms (arXiv). This paper studies the problem of testing from samples whether an unknown boolean function over the hypercube is a halfspace. The algorithm requires \(\tilde O(\sqrt{n}/\varepsilon^{7})\) random samples (which has a dependence on \(n\) which is tight up to logarithmic factors) and works for any rotation-invariant distribution, generalizing previous works that require the distribution be Gaussian or uniform.

Testing Graphs in Vertex-Distribution-Free Models, by Oded Goldreich (ECCC). While distribution-free testing has been well-studied in the context of Boolean functions, it has not been significantly studied in the context of testing graphs. In this context, distribution-free roughly means that the algorithm can sample nodes of the graph according to some unknown distribution \(D\), and must be accurate with respect to the measure assigned to nodes by the same distribution. The paper investigates various properties which may be tested with a size-independent number of queries, including relationships with the complexity of testing in the standard model.

A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice, by Hendrik Fichtenberger and Dennis Rohde (arXiv). In the \(k\)-nearest neighbor problem, we are given a set of points \(P\), and the answer to a query \(q\) is the set of the \(k\) points in \(P\) which are closest to \(q\). This paper considers the following property testing formulation of the problem: given a set of points \(P\) and a graph \(G = (P,E)\), is each point \(p \in P\) connected to its \(k\)-nearest neighbors, or is it far from being a \(k\)NN graph? The authors prove upper and lower bounds on the complexity of this problem, which are both sublinear in the number of points \(n\).