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.