After the flood of papers over the past few months, it’s reduced to “merely” six papers this October. And only two papers on distribution testing 🙂 (Update: Gautam pointed out another paper that also does distribution testing under Wasserstein distance.)

Proofs of Proximity for Distribution Testing, by Alessandro Cheisa and Tom Gur (ECCC). Take 1 on distribution testing. As usual, we have a distribution \(\mathcal{D}\) over \([n]\), a property \(\mathbf{P}\) of distributions, and a proximity parameter \(\varepsilon > 0\). But our tester is now aided by a purported proof (or a prover). If \(\mathcal{D} \in \mathbf{P}\), there must exist a proof/prover strategy that makes the tester accept. If \(\mathcal{D}\) is \(\varepsilon\)-far from \(\mathbf{P}\), for any proof/prover strategy, the tester must reject with high probability. This paper studies a number of settings: deterministic vs randomized testers, proof (a la \(\mathbb{NP}\) or \(\mathbb{MA}\)) vs provers (a la \(\mathbb{IP}\)). There are a number of very intriguing results, so here are some highlights. For every property, there is a near-linear proof that allows for \(O(\sqrt{n})\) testers. For every property, either the proof length or the tester (sample) complexity is at least \(\Omega(\sqrt{s})\), where \(s\) is the optimal complexity of a vanilla tester. But there exist prover strategies that can beat this lower bound.

Wasserstein Identity Testing, by Shichuan Deng, Wenzheng Li, and Xuan Wu (arXiv). For Take 2 on distribution testing, this paper considers the problem on continuous distributions. In all results on distribution testing, the sample complexity depends on the support size. This breaks down in this setting, so this paper focuses on identity testing according to Wasserstein distance (as opposed to \(\ell_p\)-norms). A previous paper of Do Ba-Nguyen-Nguyen-Rubinfeld also considers the same problem, where the domain is assumed to be \([\Delta]^d\). In this paper, we assume that the domain \(X\) is endowed with a metric space, to allow for the definition of Wasserstein/earthmover distance between distributions. The final result is technical, depends on the size of nets in \(X\), and is shown to be optimal for testing equality with a known distribution \(p\). The paper also gives an instance optimal for (almost) all \(p\), a la Valiant-Valiant for the discrete case.

Improved Bounds for Testing Forbidden Order Patterns, by Omri Ben-Elizer and Clément Canonne (arXiv). Any function from \(f:D \to \mathbb{R}\), where \(D\) is a total order, can be thought to induce a permutation, based on the order of function values. Consider \(f:[n] \to \mathbb{R}\) and permutation \(\pi \in S_k\). The property of \(\pi\)-free permutations is the set of \(f\) such that no restriction of \(f\) (to a subdomain of size \(k\)) induces \(\pi\). Newman et al proved that this property can be tested non-adaptively in (ignoring \(\varepsilon\)) \(O(n^{1-1/k})\) samples. Furthermore, for non-monotone \(\pi\), there is a non-adaptive \(\Omega(\sqrt{n})\) lower bound. This paper has a number of results that shed significant light on the non-adaptive complexity. The upper bound is improved to \(O(n^{1-1/(k-1)})\), and there exist a class of permutations (for every \(k\)) for which this is the optimal complexity. Furthermore, for a random \(\pi\), the paper shows a lower bound of \(\Omega(n^{1-1/(k-3)})\). There is an intriguing conjecture on the optimal complexity for any \(k\), that has an intricate dependence on the structure of \(k\). On the adaptive side, there is an interesting hierarchy for testing \((1,3,2)\)-freeness, depending on the number of rounds of adaptivity. There is an \(O(n^{1/(r+1)})\) tester with \(r\)-rounds of adaptivity, and any such tester requires \(O(n^{1/2^{r+3}})\) queries.

A \(o(d)\cdot \mathrm{poly}\log n\) Monotonicity Tester for Boolean Functions
over the Hypergrid \([n]^d\), by Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri (arXiv). Monotonicity testing has seen much progress in the past few years. This paper focuses on monotonicity testing over the hypergrid, of functions \(f:[n]^d \to \{0,1\}\). For \(n=2\) (the hypercube), the result of Khot-Minzer-Safra gives a \(\widetilde{\sqrt{d}}\) time (non-adaptive) tester. Previously, the best known tester for general \(n\) took \(O(d\log d)\) queries, by Berman-Raskhodnikova-Yaroslavtsev. This paper breaks the barrier of \(d\) queries for the hypergrid, by giving a \(O(d^{5/6}\log n)\) time tester. The main technical ingredient is a new isoperimetric inequality for the directed “augmented” hypergrid, where pairs differing on one coordinate by a power of 2 are also connected. The intriguing open question that remains is the existence of testers with query complexity sublinear in \(d\) and independent of \(n\).

Provable and practical approximations for the degree distribution using sublinear graph samples, by Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri (arXiv). The degree distribution of a simple, undirected graph \(G\) is the sequence \(\{n_d\}\), where \(n_d\) is the number of vertices of degree \(d\). The properties of the degree distribution have played a significant role in network science and the mathematical study of real-world graphs. It is often the first quantity computed in a “data analysis” of a massive graph. This paper addresses the problem of getting (bicriteria) estimates for all values of the degree distribution, in sublinear time. The main result gives sublinear time algorithms for computing degree distributions with sufficiently “fat” tails, as measured by certain fatness indices. For the important special case, when the degree distribution is a power law (\(n_d \propto 1/d^{\gamma}\)), this result yields strictly sublinear algorithms. Interestingly, the main result involves the h-index of the degree sequence, inspired by bibliographic metrics. This problem is practically important, and the paper demonstrates the quality of the sublinear algorithm in practice.

On the Complexity of Sampling Vertices Uniformly from a Graph, by Flavio Chierichetti and Shahrzad Haddadan (arXiv). This paper isn’t your traditional property testing paper, but is very relevant to those of us interested in graph property testing. One common query model in graph property testing is access to uniform random vertices. In practice though (think of a graph like the Facebook friendship network or the web graph), this is quite challenging. We typically have access to a few seed vertices, and we can “crawl” the graph. A natural approach is to perform a random walk (in the hope of mixing quickly) to generate random vertices. We might attempt rejection sampling or Metropolis-Hastings on top of that to get uniform random vertices. A recent result of Chierichetti et al give an algorithm for this problem using \(O(t_{mix} d_{avg})\) samples, where \(t_{mix}\) is the mixing time (of the random walk on the graph) and \(d_{avg}\) is the average degree. This paper proves that this bound is optimal, for most reasonable choices of these parameters.