December was indeed a merry month for property testing, with seven new papers appearing online.* Let’s hope the trend continues!

Cube vs. Cube Low Degree Test, by Amey Bhangale, Irit Dinur, and Inbal Livni Navon (ECCC). This work provides a new and improved analysis of the “low-degree test” of Raz and Safra, tightening the dependence on the alphabet size of the soundness parameter. Specifically, the goal is as follows: given query access to the encoding of a function \(f\colon \mathbb{F}^m\to \mathbb{F}\) as a “cube table,” decide whether \(f\) is a low-degree polynomial (i.e., of degree at most \(d\)). With direct applications to PCP theorems, this question has a long history; here, the authors focus on a very simple and natural test, introduced by Raz–Safra and Arora–Sudan. In particular, they improve the soundness guarantee, which previously required the error to be at least \(\textrm{poly}(d)/\mathbb{F}^{1/8}\), to obtain a dependence on the field size which is only \(\mathbb{F}^{-1/2}\).

Robust Multiplication-based Tests for Reed-Muller Codes, by Prahladh Harsha and Srikanth Srinivasan (arXiv). Given a function \(f\colon \mathbb{F}_q^n\to\mathbb{F}_q\) purported to be a degree-\(d\) polynomial, deciding whether this is indeed the case is a question with applications to hardness of approximation and — as the title strongly hints— to testing of Reed—Muller codes. Here, the authors generalize and improve on a test originally due to Dinur and Guruswami, improving on the soundness: that is, they show a robust version of the soundness guarantee of this multiplication test, answering a question left open by Dinur and Guruswami.

A Note on Testing Intersection of Convex Sets in Sublinear Time, by Israela Solomon (arXiv). In this note, the author addresses the following testing question: given \(n\) convex sets in \(\mathbb{R}^d\), distinguish between the case where (i) the intersection is non-empty, and (ii) even after removing any \(\varepsilon n\) sets, the intersection is still empty. Through the use of a generalization of Helly’s Theorem due Katchalski and Liu (1979), the author then provides and analyzes an algorithm for this question, with query complexity \(O(\log 1/(d\varepsilon))\).

A Characterization of Constant-Sample Testable Properties, by Eric Blais and Yuichi Yoshida (arXiv). A lot of work in property testing has been to understand which properties can be locally tested, i.e. admit testers with constant query complexity. Here, the authors tackle — and answer — the variant of this question in the sample-based testing model, that is restricting the ability of the algorithm to only obtain the value of the function on independently and uniformly distributed locations. Namely, they provide a full characterization of the properties of Boolean-valued function which are testable with constant sample complexity, resolving the natural question of whether most properties are easily tested from samples only. As it turns out, only those properties which are (essentially) \(O(1)\)-part-symmetric have this nice testability — where a property \(\mathcal{P}\) is \(k\)-part-symmetric if one can divide the input variables in \(k\) blocks, such that membership to \(\mathcal{P}\) is invariant by permutations inside each block.

The last three are all works on distribution testing, and all concerned with the high-dimensional case. Indeed, most of the distribution testing literature so far has been focusing in probability distributions over arbitrary discrete sets or the one-dimension ordered line; however, when trying to use these results in the (arbitrary) high-dimensional case on is subjected to the curse of dimensionality. Can one leverage (presumed) structure to reduce the cost, and obtain computationally and sample-efficient testers?

Testing Ising Models, by Costis Daskalakis, Nishanth Dikkala, and Gautam Kamath (arXiv). In this paper, the authors take on the above question in the context of Markov Random Fields, and more specifically in the Ising model. Modeling the (unknown) high-dimensional distributions as Ising models with some promise on the parameters, they tackle the two questions of identity and independence testing; respectively, “is the unknown Ising model equal to a fixed, known reference distribution?” and “is the high-dimensional, a priori complex distribution a product distribution?”. They obtain both testing algorithms and lower bounds for these two problems, where the soundness guarantee sought is in terms of the symmetrized Kullback—Leibler divergence (a notion of distance more stringent that the statistical distance).

Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing, by Costis Daskalakis and Qinxuan Pan (arXiv). Another natural model to study structured high-dimensional distribution is that of Bayesian networks, that is directed graphs providing a succinct description of the dependencies between coordinates. This paper studies the closeness testing problem (testing if two unknown distributions are equal or far, with regard to the usual statistical distance) for Bayesian networks, parameterized by the dimension, alphabet size, and (promise on the) maximum in-degree of the unknown Bayes net. At its core is a new inequality relating the (squared) Hellinger distance of two Bayesian networks to the sum of the (squared) Hellinger distances between their marginals.

Testing Bayesian Networks, by Clément Canonne, Ilias Diakonikolas, Daniel Kane, and Alistair Stewart (arXiv). Tackling the testing of Bayesian networks as well, this second paper considers two of the most standard testing questions — identity (one-unknown) and closeness (two-unknown) testing — under various assumptions, in order to pinpoint the exact sample complexity in each case. Specifically the goal is to see when (and under which natural restrictions) does testing become easier than learning for Bayesian networks, focusing on the dimension and maximum in-degree as parameters.

* As usual, if we forgot one or you find imprecisions in our review of a paper, please let us now in the comments below.

September has just concluded, and with it the rise of Fall in property testing: no less than 5 papers* this month.

Removal Lemmas for Matrices, by Noga Alon and Omri Ben-Eliezer (arXiv). The graph removal lemma, and its many variants and generalizations, is a cornerstone in graph property testing (among others), and is a fundamental ingredient in many graph testing results. In its simplest form, it states that  for any fixed \(h\)-vertex pattern \(H\) and \(\varepsilon > 0\),  there is some constant \(\delta=\delta(\varepsilon)\) such that any graph \(G\) on \(n\) vertices containing at most \(\delta n^h\) copies of \(H\) can be “fixed” (made \(H\)-free) by removing at most \(\varepsilon n^2\) edges.
The authors introduce and establish several analogues of this result, in the context of matrices. These matrix removal lemmas have direct implications in property testing (discussed in Section 1.2); for instance, they imply constant-query testing of \(F\)-freeness of (binary) matrices, where \(F\) is any family of binary matrices closed under row permutations.

Improving and extending the testing of distributions for shape-restricted properties, by Eldar Fischer, Oded Lachish, and Yadu Vasudev (arXiv). Testing membership to a class (family) is a very natural question in distribution testing, and one which has received significant attention lately. In this paper, the authors build on, improve, and generalize the techniques of Canonne, Diakonikolas, Gouleakis, and Rubinfeld (2016) to obtain a generic, one-size-fits-all algorithm for this question. They also consider the same question in the “conditional oracle” setting, for which their ideas yield significantly more sample-efficient algorithms. At the core of their approach is a better and simpler learning procedure for families of distributions that enjoy some decomposability property.

The Bradley―Terry condition is \(L_1\)–testable, by Agelos Georgakopoulos and  Konstantinos Tyros (arXiv). An incursion in probability models: say that the directed weighted graph \(((V,E),w)\) on \(n\) vertices, with \(w\colon E_n\to[0,1]\) such that \(w(x,y)=w(y,x)\) for all \((x,y)\in V^2\), satisfies the Bradley—Terry condition if there exists an assignment of probabilities \((a_x)_{x\in V}\) such that

\(\qquad\displaystyle \frac{w(x,y)}{w(y,x)} = \frac{a_x}{a_y}\)

for all \((x,y)\in V^2\). This condition captures whether such a graph corresponds to a Bradley—Terry tournament.
This paper considers this characterization from a property testing point of view: that is, it addresses the task of testing, in the \(L_1\)-sense of Berman, Raskhodnikova, and Yaroslavtsev (2012), if a \(((V,E),w)\) satisfies the Bradley—Terry condition (or is far from any such graph).

On SZK and PP, by Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan (arXiv, ECCC). Another (unexpected) connection! This work proves query and communication complexity separations between two complexity classes, \(\textsf{NISZK}\) (non-interactive statistical zero knowledge) and \(\textsf{UPP}\) (a generalization of \(\textsf{PP}\) with unbounded coin flips, and thus arbitrary gap in the error probability). While I probably cannot even begin to list all that goes over my head in this paper, the authors show in Section 2.3.2 some implications of their results for property testing, for instance in distribution testing. In more detail, their results yield some lower bounds on the sample complexity of (tolerant) property testers with success probability arbitrarily close to \(1/2\) (as opposed to the “usual” setting of \(1/2+\Omega(1)\)).

Quantum conditional query complexity, by Imdad S. B. Sardharwalla, Sergii Strelchuk, and Richard Jozsa (arXiv). Finally, our last paper of the list deals with both quantum algorithms and distribution testing, by introducing a new distribution testing model in a quantum setting, the quantum conditional oracle. This model, the quantum analogue of the conditional query oracle of Chakraborty et al. and Canonne et al., allows the (quantum) testing algorithm to get samples from the probability distribution to test, conditioning on chosen subsets of the domain.
In this setting, they obtain speedups over both (i)  quantum “standard” oracle and (ii)  “classical” conditional query testing for many distribution testing problems; and also consider applications to quantum testing of Boolean functions, namely balancedness.

* As usual, in case we missed or misrepresented any, please signal it in the comments.

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.

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.