We were able to find four new papers for May 2019 — as usual, please let us know if we missed any!
EDIT: We did, in fact, miss one paper, which is the bottom one listed below.
On Local Testability in the Non-Signaling Setting, by Alessandro Chiesa, Peter Manohar, and Igor Shinkar (ECCC). This paper studies testability of a certain generalization of (distributions over) functions, known as \(k\)-non-signalling functions, objects which see use in hardness of approximation and delegation of computation. Prior work by the authors show the effectiveness of the linearity test in this setting, leading to the design of PCPs. On the other hand, in this work, the authors show that two types of bivariate tests are ineffective in revealing low-degree structure of these objects.
Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries, by Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai (arXiv). This work, apparently simultaneous with the one by Forster and Yang that we covered last month, also studies the problem of locally computing cuts in a graph. The authors also go further, and study approximation algorithms for the same problems. Inspired by the connections to property testing in the work of Forster and Yang, they apply these approximation algorithms to get even more query-efficient algorithms for the problems of testing \(k\)-edge- and \(k\)-vertex-connectivity.
Testing Graphs against an Unknown Distribution, by Lior Gishboliner and Asaf Shapira (arXiv). This paper studies graph property testing, under the vertex-distribution-free (VDF) model, as recently introduced by Goldreich. In the VDF model, rather than the ability to sample a random node, the algorithm has the ability to sample a node from some unknown distribution, and must be accurate with respect to the same distribution (reminiscent of the PAC learning model). In Goldreich’s work, it was shown that every property which is testable in the VDF model is semi-hereditary. This work strengthens this statement and proves a converse, thus providing a characterization: a property is testable in the VDF model if and only if it is both hereditary and extendable. These descriptors roughly mean that the property is closed under both removal and addition of nodes (with the choice of addition of edges in the latter case). This is a far simpler characterization than that of properties which are testable in the standard model, which is a special case of the VDF model.
Private Identity Testing for High-Dimensional Distributions, by Clément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakynthinou (arXiv). This work continues a recent line on distribution testing under the constraint of differential privacy. The settings of interest are multivariate distributions: namely, product distributions over the hypercube and Gaussians with identity covariance. An application of a statistic of CDKS, combined with a Lipschitz extension from the set of datasets likely to be generated by such structured distributions, gives a sample-efficient algorithm. A time-efficient version of this extension is also provided, at the cost of some loss in the sample complexity. Some tools of independent interest include reductions between Gaussian mean and product uniformity testing, balanced product identity to product uniformity testing, and an equivalence between univariate and “extreme” product identity testing.
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model, by Oded Goldreich (arXiv). Another work on the vertex-distribution-free (VDF) model, as described above. In this one, Goldreich considers an augmentation of the model, where the algorithm is further allowed to query the probability of each node. With this augmentation, he gives \(\tilde O(\sqrt{n})\)-time algorithms for testing bipartiteness and cycle-free-ness, where \(n\) is the “effective support” of the distribution. That is, \(n\) is the number of nodes in the graph after discarding the nodes with minimal probability until \(\varepsilon/5\) mass is removed.