News for February 2016! Another take on distribution testing, exciting stuff about generating random graphs, and distributed property testing.

Sublinear Random Access Generators for Preferential Attachment Graphs by Guy Even, Reut Levi, Moti Medina, and Adi Rosén (ArXiv). A major aspect of research in “network science” and applied large graph analysis is random graph models. A classic example is the Barabasi-Albert preferential attachment (PA) model, that attempts to model graphs that appear in the real-world. The model is inherently sequential, in that vertices “arrive” in order and connect to other vertices according to a specified distribution. It was not clear how to generate a PA graph in parallel, or how one can construct a local view of a PA graph without constructing all of it. Not clear, that is, until this paper. This really cool result shows the following. Suppose we want to construct an \(n\) vertex PA graph. One can basically query the adjacency list of any vertex in \(poly(\log n)\) time, without constructing the graph! The PA graph is implicitly constructed through the queries. This is really interesting because PA graphs (at least conceptually) are created sequentially, and the order of vertex arrival fundamentally affects the graph structure.

The Uniform Distribution is Complete with Respect to Testing Identity to a Fixed Distribution by Oded Goldreich (ECCC) . This is a follow up to a recent result by Diakonikolas and Kane (covered last month!). This paper reduces testing equality (of a distribution) to a fixed distribution, to the special case to when the fixed distribution is uniform. The notions of reduction in distribution testing were exploited by Diakonikolas and Kane to get optimal testers. While this new paper does not give new bounds, it gives a clean and simplified approach for testing distribution equality. This paper came out of Oded’s lecture notes, and has a nice expository feel to it.

Fast Distributed Algorithms for Testing Graph Properties by Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev (ArXiv) . Connections between distributed algorithms and property testing have been unearthed in the past (most explicitly by Parnas and Ron). This paper directly solves graph property testing problems in the distributed setting. For dense graph testing, it is known that any (constant-query) testing algorithm algorithm can be made non-adaptive, and thus can be simulated in the distributed setting. The results for testing bipartiteness in the sparse graph model are quite interesting, because existing property testers use random walks. This paper gives a distributed implementation of multiple random walks from all vertices, and controls the total congestion of the implementation. This leads to a \(O(\log n)\)-round bipartiteness tester.

In the first month of 2016 we had a couple of interesting papers in property testing.

Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation by Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis, John Peebles, Ronitt Rubinfeld and Anak Yodpinyanee (ArXiv) . Estimating the number of subgraphs of a fixed form in a given graph has been a very well studied problem in the subject of property testing.  The classical example is counting the number of triangles in a graph. Usually we assume we can sample the vertices uniformly at random. In this paper a new model of query has been considered where one can sample the edges uniformly at random. Under this model it is shown that the query complexity can be reduced when the goal is to estimate the number of p-stars in a graph. It would be interesting to see if this model helps to get better query complexity for other problems also. Depending on the application different query models can be relevant and hence understanding these different query models are essential.

A New Approach for Testing Properties of Discrete Distributions by Ilias Diakonikolas and Daniel M. Kane (ArXiv) . Testing properties of distribution has been a central topic in our field. Not only are these problems interesting they also has been applied as subroutines to many other testing algorithms. In the literature a number of different properties like testing whether a distribution is uniform or testing whether two distributions are identical or testing if two distributions are independent and many more has been studied. In most of the properties the distance measure is the L_1 measure. In this paper a unifying technique to obtain testing algorithms for properties of distributions in the L_1 distance has been given by converting them to the problem of testing in the L_2 distance and applying standard testing algorithms in the L_2 distance. This approach would hopefully help us simplify the various algorithms in distribution testing.

(Updating post with an additional paper that we missed in our first posting. Sorry! Feel free to email us at little.oh.of.n@gmail.com to inform us of papers we should mention.)

We’ve got exciting new in November! Optimal results for testing of monotone conjunctions, a new lower bound for monotonicity testing (yay!), and new lower bounds for Locally Testable Codes.

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions by Xi Chen and Jinyu Xie (arxiv). Consider functions \(f: \{0,1\}^n \rightarrow \{0,1\}\) (amen), and the basic property of being a monotone conjunction. Our notion of distance is with respect to a distribution \(\mathcal{D}\), so the distance between functions \(f\) and \(g\) is \(\mathop{Pr}_{x \sim \mathcal{D}} [f(x) \neq g(x)]\). In the distribution-free testing model, the tester does not know the distribution \(\mathcal{D}\), but is allowed samples from \(\mathcal{D}\). When \(\mathcal{D}\) is uniform, this coincides with standard property testing. There can be significant gaps between standard and distribution-free testing, evidenced by conjunctions. Parnas, Ron, and Samorodnitsky proved that monotone conjunctions can be tested in the vanilla setting in time independent of \(\mathcal{n}\), while Glasner-Servedio prove a \(\Omega(n^{1/5})\) lower bound for distribution-free testing. This paper provides a one-sided, adaptive distribution-free tester that makes \(\widetilde{O}(n^{1/3})\) queries, and they also prove a matching (up to polylog terms and \(\epsilon\)-dependencies) two-sided, adaptive lower bound. This is a significant improvement on the previous upper bound of \(\widetilde{O}(\sqrt{n})\) of Dolev-Ron, as well as over the previous lower bound. Furthermore, the results of this paper hold for general conjunctions.

A Polynomial Lower Bound for Testing Monotonicity by Aleksandrs Belovs and Eric Blais (arxiv). Surely the reader needs little introduction to testing monotonicity of Boolean functions, and a previous Open Problem post should help. A quick summary: we want to test monotonicity of \(f:\{0,1\}^n \rightarrow \{0,1\}\). The best upper bound is the \(\widetilde{O}(\sqrt{n})\) non-adaptive, one-sided tester of Khot et al. There is a matching, non-adaptive lower bound (up to polylog terms) by Chen et al, implying the best-known adaptive lower bound of \(\Omega(\log n)\). Can adaptivity help? This paper proves an adaptive lower bound of \(\Omega(n^{1/4})\). Exciting! The approach of Chen et al is to focus on monotonicity of linear threshold functions (technically, regular LTFS, where the weights are bounded). The authors show that this property can be tested in \(\mathop{poly}(\log n)\) time, shooting down hopes of extending the LTF approach for adaptive lower bounds. The key insight is to work with the distribution of Talagrand’s random DNF instead, which is the most noise sensitive DNF. (Talagrand strikes again. He helps the upper bound, he helps the lower bound.) Perturbations of this DNF lead to non-monotone functions, the paper proves that these distributions cannot be distinguished in \(o(n^{1/4})\) queries.

Lower bounds for constant query affine-invariant LCCs and LTCs by Arnab Bhattacharyya and Sivakanth Gopi (arxiv). Think of any code as a set/property of codewords in the domain \(\Sigma^N\). Such a code is an \(r\)-LTC if it has an \(r\)-query property tester. An \(r\)-LCC is has the property that, given any \(x \in \Sigma^n\) sufficiently close to a codeword, one can determine any coordinate of the codeword using \(r\)-queries. A fundamental question is to understand the length of LCCs and LTCS, or alternately (fixing \(\Sigma^N\)) determining the largest possible set of codewords. Existing constructions typically have much symmetry, either linear or affine invariance. (Check out Arnab Bhattacharyya’s survey on affine invariant properties for more details.) It is convenient to think of any codeword as a function \(f: [N] \rightarrow \Sigma\), and furthermore, think of \([N]\) as a vector space \(\mathbb{K}^n\). The best known construction of Guo, Kopparty, and Sudan yields (affine-invariant) LCCs of size \(\exp(\Theta(n^{r-1}))\) and LTCs of size \(\exp(\Theta(n^{r-2}))\) (many dependences on \(\mathbb{K}\), the rate, etc. are hidden in the big-Oh). This paper show that these bounds are actually the best achievable by any affine-invariant code. (Previous lower bounds of Ben-Sasson and Sudan only held for linear codes.) The intriguing and wide-open question is to prove such lower bounds without affine invariance.

Alas! A dry month, with no property testing or sublinear papers. Maybe next month…

We have a couple of papers this month.

This month saw more development on testing properties of distributions and a result with intriguing connections to property testing. And for readers who may have missed it, Clément Canonne and Gautam Kamath wrote an engaging survey of some recent work on testing properties of distribution here.

Optimal algorithms and lower bounds for testing closeness of structured distributions by Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin (arXiv). One of the fundamental results in testing properties of distributions is that if we want to estimate the (\(L_1\)) distance between two unknown distributions on a domain of size \(n\) up to some constant additive factor,  we need to draw \(O(n^{2/3})\) samples from these distributions, and this sample complexity is tight in general. But what if we consider the same problem in the setting where we are promised that the distributions come from some (known) class of distribution? This paper shows that, for many natural classes of distributions, we can obtain much more efficient algorithms for testing the closeness of distributions in this setting.

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions by Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, and Avi Wigderson (arXiv). The (maximum) sensitivity of a Boolean function \(f : \{0,1\}^n \to \{0,1\}\) is the size of the largest set \(S \subseteq [n]\) such that there is an input \(x \in \{0,1\}^n\) for which \(f(x) = f(y)\) for every input \(y\) obtained by flipping the value of the \(i\)th coordinate of \(x\) for some \(i \in S\). One of the results in this paper shows that functions with low sensitivity can be locally self-corrected: given query access to a function \(r : \{0,1\}^n \to \{0,1\}\) that is close to a function \(f\) with low sensitivity (think of \(r\) as a corrupted version of \(f\)), there is an algorithm that for any input $x \in \{0,1\}^n$, queries \(r\) on a few inputs and outputs with high probability the value \(f(x)\). This notion of local self-correction is of course closely related to locally-decodable codes; it is also one of the fundamental techniques used to obtain many results in property testing as well (see for example Chapter 3 of Dana Ron’s survey). Can this result, or the techniques used to obtain it, also yield new results in property testing?