# News for October 2018

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$$.