News for May 2016

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.

Call for feedback: upcoming “Introduction to Property Testing”

Forwarding an announcement by Oded Goldreich:

I would like to seek the help of this community regarding my forthcoming book Introduction to Property Testing (see http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html). Specifically, I would be grateful for feedback regarding any aspect and part of the current text, although detailed comments are likely to be more helpful at this time than suggestions for drastic and/or structural changes. Please do not shy from indicating relevant works that may be mentioned (rather than described in detail), since it is quite possible that I was not aware of them or forgot to mention them (rather than chose not to include a detailed description due to various considerations).

Since I am likely to continue revising the text and posting the revisions on the website, please indicate the text-locations to which you refer in a manner that is most robust to revision (e.g., indicate relative location with respect to sectioning and/or theorem-environment numbers rather than with respect to page numbers).

News for April 2016

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)\).

Open problem for April 2016

As open problems of the month, we state here the two questions discussed in our recent guest post by Oded Goldreich:

Open Problem 1 (obtaining a one-sided error reduction): The reduction from testing affinity of a subspace to that of testing affinity of a function has two-sided error probability. We wonder whether a one-sided error reduction of similar complexity can be found.

Note that this will yield a one-sided error tester for affinity, which we believe is not known. Actually, we would also welcome a two-sided error reduction that, when combined with the linearity tester, yields a tester of complexity \(O(1/\epsilon)\) rather than \(\tilde{O}(1/\epsilon)\).

Turning to the task of testing monomials, we recall that the solution of [PRS02] is based on employing self-correction to the following test that refers to the case that \(H=\{x:AX=b\}\) is an \((\ell-k)\)-dimensional affine space. Basically, the test selects a random \(x\in H\) and a random \(y\in\{0,1\}^\ell\), and checks whether it holds that \(y\in H\) if and only if \(x\wedge y \in H\), where \(\wedge\) denotes the bit-by-bit product of vectors. It is painfully shown in [5] that if \(H\) is not a translation by \(1^\ell\) of an axis-aligned linear space, then the check fails with probability \(\Omega(2^{-k})\). Furthermore, it is shown that for a constant fraction of the \(x\)’s (in \(H\)), the check fails on a \(\Omega(2^{-k})\) fraction of the \(y\)’s (in \(\{0,1\}^\ell\)). This strengthening is important, since selecting \(x\in H\) uniformly requires \(\Theta(2^k)\) trials. Recall that proving the foregoing assertion for \(k=1\) is quite easy (cf. [5]), which leads us to ask

Open Problem 2 (can a simpler proof be found for the case of \(k>1\)): Is there a relatively simple reduction of the foregoing claim for general \(k\) to the special case of \(k=1\)?

[PRS02] M. Parnas, D. Ron, and A. Samorodnitsky. Testing Basic Boolean Formulae. SIAM Journal on Disc. Math. and Alg., Vol. 16 (1), pages 20–46, 2002.

Guest Post: Oded Goldreich, “Reducing testing affine spaces to testing linearity”

[We are delighted to have this month a blog post by Oded Goldreich, on a reduction from testing affinity of subspaces to testing linearity of Boolean functions. Oded also gave us open problems directly related to this post.]

We consider the task of testing whether a Boolean function \(f\colon \{0,1\}^\ell\to\{0,1\}\) is the indicator function of an \((\ell-k)\)-dimensional space. An optimal tester for this property was presented by Parnas, Ron, and Samorodnitsky (SIDMA, 2002), by mimicking the celebrated linearity tester (of Blum, Luby and Rubinfeld, JCSS, 1993) and its analysis. We show that this task can be reduced to testing the linearity of a related function \(g\colon\{0,1\}^\ell\to\{0,1\}^k\), yielding an almost optimal tester.

Continue reading

News for March 2016

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

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.

Lecture Notes on Property Testing

(Update: Krzysztof pointed out the resources at sublinear.info, which we forgot to mention. It makes for sense for all of this information to be there. We’ve added links there, and would urge our readers to post more information there. Beats having it in half-baked blogposts!)

Despite the relative maturity of property testing (more than a decade old!), we still lack a good textbook on the subject. At least, I definitely feel the need when I’m talking to interested students. I end up pointing to a bunch of papers, all with their own notation. We now have numerous courses being taught, so that certainly helps. And Oded Goldreich just pointed out his notes. So here’s a summary of stuff that I have found. Please let us know if you have other sources, including your own courses!

Oded Goldreich’s lecture notes
Ronitt Rubinfeld’s collection of surveys
Sofya Raskhodnikova’s course notes at Penn State
Eric Price’s course notes at UT Austin
Grigory Yaroslavtsev’s crash course at the University of Buenos Aires
Rocco Servedio’s course notes at Columbia