After a few slow months, property testing is back with a bang! This month we have a wide range on results ranging from classic problems like junta testing to new models of property testing.

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism, by Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, and Dana Ron (arXiv). The problem of junta testing requires little introduction. Given a boolean function \(f:\{-1,+1\}^n \mapsto \{-1,+1\}\), a \(k\)-junta only depends on \(k\) of the input variables. A classic problem has been that of property testing \(k\)-juntas, and a rich line of work (almost) resolves the complexity to be \(\Theta(k/\epsilon)\). But what of tolerant testing, where we want to tester to accept functions close to being a junta? Previous work has shown that existing testers are tolerant, but with extremely weak parameters. This paper proves: there is a \(poly(k/\epsilon)\)-query tester that accepts every function \(\epsilon/16\)-close to a \(k\)-junta and rejects every function \(\epsilon\)-far from being a \(4k\)-junta. Note that the “gap” between the junta classes is a factor of 4, and this is the first result to achieve a constant gap. The paper also gives testers when we wish to reject functions far from being a \(k\)-junta (exactly matching the definition of tolerant testng), but the tester has an exponential dependence on \(k\). The results have intriguing connections with isomorphism testing, and there is a neat use of constrained submodular minimization.

Testing Pattern-Freeness, by Simon Korman and Daniel Reichman (arXiv). Consider a string \(I\) of length \(n\) and a “pattern” \(J\) of length \(k\), both over some alphabet \(\Sigma\). Our aim is to property test if \(I\) is \(J\)-free, meaning that \(I\) does not contains \(J\) as a substring. This problem can also be generalized to the 2-dimensional setting, where \(I\) and \(J\) are matrices with entries in \(\Sigma\). This formulation is relevant in image testing, where we need to search for a template pattern in a large image. The main results show that these testing problems can be solved in time \(O(1/\epsilon)\), with an intriguing caveat. If the pattern \(J\) has at least \(3\) distinct symbols, the result holds. If \(J\) is truly binary, then \(J\) is not allowed to be in a specified set of forbidden patterns. The main tool is a modification lemma that shows how to “kill” a specified occurrence of \(J\) without introducing a new one. This lemma is not true for the forbidden patterns, resulting in the dichotomy of the results.

Erasure-Resilient Property Testing, by Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma (arXiv). Property testing begins with a query model for \(f: \mathcal{D} \mapsto \mathcal{R}\), so we can access any \(f(x)\). But what if an adversary corrupted some fraction of the input? Consider monotonicity testing on the line, so \(f: [n] \mapsto \mathbb{R}\). We wish to test if \(f\) is \(\epsilon\)-far from being monotone, but the adversary corrupts/hides an \(\alpha\)-fraction of the values. When we query such a position, we receive a null value. We wish to accept if there exists some “filling” of the corrupted values that makes \(f\) monotone, and reject if all “fillings” keep \(f\) far from monotone. It turns out the standard set of property testers are not erasure resilient, and fail on this problem. This papers gives erasure resilient testers for properties like monotonicity, Lipschitz continuity, and convexity. The heart of the techniques involves a randomized binary tree tester for the line that can avoid the corrupted points.

Partial Sublinear Time Approximation and Inapproximation for Maximum Coverage, by Bin Fu (arXiv). Consider the classic maximum coverage problem. We have \(m\) sets \(A_1, A_2, \ldots, A_m\) and wish to pick the \(k\) of them with the largest union size. The query model allows for membership queries, cardinality queries, and generation of random elements from a set. Note that the size of the input can be thought of as \(\sum_i |A_i|\). Can one approximate this problem without reading the full input? This paper gives a \((1-1/e)\)-factor approximation that runs in time \(poly(k)m\log m\), and is thus sublinear in the input size. The algorithm essentially implements a greedy approximation algorithm in sublinear time. It is shown the the linear dependence on \(m\) is necessary: there is no constant factor approximation that runs in \(q(n) m^{1-\delta}\) (where \(n\) denotes the maximum cardinality, \(q(\cdot)\) is an arbitrary function, and \(\delta > 0\)).

Local Testing for Membership in Lattices, by Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu (arXiv). Inspired by the theory of locally testable codes, this paper introduces local testing in lattices. Given a set of basis vectors \(b_1, b_2, \ldots\) in \(\mathbb{Z}^n\), the lattice \(L\) is the set of all integer linear combinations of the basic vectors. This is the natural analogue of linear error correcting codes (where everything is done over finite fields). Given some input \(t \in \mathbb{Z}^n\), we wish to determine if \(t \in L\), or is far (defined through some norm) from all vectors in \(L\), by querying a constant number of coordinates in \(t\). We assume that \(L\) is fixed, so it can be preprocessed arbitrarily. This opens up a rich source of questions, and this work might be seen as only the first step in this direction. The papers shows a number of results. Firstly, there is a family of “code formula” lattices for which testers exists (with almost matching lower bounds). Furthermore, with high probability over random lattices, testers do not exist. Analogous to testing codes, if a constant query lattice tester exists, then there exists a canonical constant query tester.

This month isn’t the most exciting for property testing. Just one paper to report (thanks to Clément for catching!), of which only a minor part is actually related to property testing.

Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximation, by Insu Han, Dmitry Malioutov, Haim Avron, and Jinwoo Shin (arXiv). The main results of the paper deal with approximating the trace of matrix functions. Consider symmetric matrix \(M \in \mathbb{R}^{d\times d}\), with eigenvalues \(\lambda_1, \lambda_2, \ldots, \lambda_d\). The paper gives new algorithms to approximate \(\sum_i f(\lambda_i)\). Each “operation” of the algorithm is a matrix-vector product, and the aim is to minimize the number of such operations. The property testing application is as follows. Suppose we wish to test if \(M\) is positive-definite (all \(\lambda_i > 0\)). We consider a matrix \(\epsilon\)-far from being positive-definite if the smallest eigenvalue is less than \(-\epsilon \|M\|_F = -\epsilon \sum_i \lambda^2_i\). The main theorems in this paper yield a testing algorithm (under this definition of distance) that makes \(o(d)\) matrix-vector products. While this is not exactly sublinear under a standard query access model, it is relevant when \(M\) is not explicitly represented and the only access is through such matrix-vector product queries.

Last month witnessed two new property testing papers go online, which May be of interest to the community.

Reducing testing affine spaces to testing linearity, by Oded Goldreich (ECCC). In his recent guest post, the author outlined a reduction between testing if a Boolean function is an \((n-k)\)-dimensional affine subspace of \(\{0,1\}^n\), and testing linearity of functions \(f\colon\{0,1\}^n\to \{0,1\}\). This preprint encompasses details of this reduction, as part as a general approach to testing monomials (resolving along the way one of the open problems from April). Namely, it shows that testing if \(f\) is a \(k\)-monomial can be reduced to testing two properties, of \(f\) and of a (related) function \(g\colon\{0,1\}^n\to \{0,1\}^k\). Moreover, it establishes that the general case (\(k\geq 1\)) of the second part  can itself be reduced to the simpler case (\(k=1\)), giving a unified argument.

Testing Equality in Communication Graphs, by Noga Alon, Klim Efremenko, Benny Sudakov (ECCC). Given a connected graph on \(k\) nodes, where each node has an \(n\)-bit string, how many bits of communication are needed to test if all strings are equal? This paper investigates this problem for many interesting graphs, resolving the complexity up to lower order terms. For example, if the graph is Hamiltonian, they show that \(\frac{kn}{2} + o(n)\) bits are sufficient, while at least \(\frac{kn}{2}\) bits are required.

Edit (06/16): updated the description of the first preprint, which was not entirely accurate.

April has been kind to us, providing us with a trio of new papers in sublinear algorithms. Also, in case you missed them, be sure to check out Oded Goldreich’s guest post and the associated open problem.

Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time, by Michael Kapralov (ArXiv). There is a rich line of work focused on going beyond the celebrated Fast Fourier Transform algorithm by exploiting sparsity in the signal’s Fourier representation. While the one-dimensional case is very well understood, results in higher dimensions have either been lacking with respect to time complexity, sample complexity, or the approximation guarantee. This work is the first to give an algorithm which runs in sublinear time, has near-optimal sample complexity, and provides an arbitrarily accurate approximation guarantee for the multivariate case.

Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection, by Talya Eden, Dana Ron, C. Seshadhri (ArXiv). This work revisits the problem of approximating the moments of the degree distribution of a graph. Prior work has shown that the \(s\)-th moment of the degree distribution can be computed with \(\tilde O(n^{1 – 1/(s+1)})\) queries, which is optimal up to \(\mathrm{poly}(\log n)\) factors. This work provides a new algorithm which requires only \(\tilde O(n^{1 – 1/s})\) queries on graphs of bounded arboricity, while still matching previous near-optimal bounds in the worst case. Impressively, the algorithm is incredibly simple, and can be stated in just a few lines of pseudocode.

A Local Algorithm for Constructing Spanners in Minor-Free Graphs, by Reut Levi, Dana Ron, Ronitt Rubinfeld (ArXiv). This paper addresses the problem of locally constructing a sparse spanning graph. For an edge \(e\) in a graph \(G\), one must determine whether or not \(e\) is in a sparse spanning graph \(G’\) in a manner that is consistent with previous answers. In general graphs, the complexity of this problem is \(\Omega(\sqrt{n})\), leading to the study of restricted families of graphs. In minor-free graphs (which include, for example, planar graphs), existing algorithms require \((d/\varepsilon)^{\mathrm{poly}(h)\log(1/\varepsilon)}\) queries and induce a stretch of \(\mathrm{poly}(d, h, 1/\varepsilon)\), where \(d\) is the maximum degree, \(h\) is the size of the minor, and \(G’\) is of size at most \((1 + \varepsilon)n\). The algorithm in this paper shows the complexity of this problem to be polynomial, requiring only \(\mathrm{poly}(d, h, 1/\varepsilon)\) queries and inducing a stretch of \(\tilde O(h \log (d)/\varepsilon)\).

While March 2016 has been rather low in terms of property testing, we did see a new paper appear:

A Note on Tolerant Testing with One-Sided Error, by Roei Tell (ECCC). A natural generalization of property testing is that of tolerant testing, as introduced by Parnas, Ron, and Rubinfeld [PRR06]: where the tester still must reject all objects that are far from satisfying the property, but now also has to accept those that are sufficiently close (all that with constant probability). In this work is considered the question of one-sidedness of tolerant testers: namely, is it possible to only err on the farness side, but accept close output with probability one? As it turns out, it is not — the author shows that any such one-sided tolerant tester, for basically any property of interest, must essentially query the whole input…

Universal Locally Testable Codes, by Oded Goldreich and Tom Gur (ECCC). In this work, the authors introduce and initiate the study of an extension of locally testable codes they name universal locally testable codes (universal-LTC). At a high-level, a universal-LTC (with regard to a family of functions \(\cal F\)) is a locally testable code \(C\) “for which the restrictions (subcodes) of \(C\) by functions in \(\cal F\) are also locally testable.” In other terms, one is then able to test efficiently, given an encoded string \(w\), if (i) \(w=C(x)\) for some \(x\); but also, for any \(f\in \cal F\), if (ii) \(w=C(x)\) for some \(x\) that satisfies \(f(x)=1\).

Edit (04/06): added the work of Goldreich and Gur, which was overlooked in our first version of the article.

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.