10 papers in May! With a mix of testing for logic, quantum, codes, and distribution testing, this was a very prolific and well-rounded month. Let’s get to it, in no particular order!
Constant time testability of first-order logic with modulo counting on finitary graphs, by Isolde Adler, Jenny Stimpson (arXiv). This paper is concerned with testing, in the bounded-degree graph model, graph properties which can be expressed in first-order (resp. second-order monadic) logic with additional modulo quantifiers. The main result is a “meta-theorem” which states that every such property concerning graphs with a uniform (constant) bound on the size of connected components can be tested with a constant number of queries.
Tolerant Testing for Unique Games, by Yuichi Yoshida (arXiv). The property testing version of Unique Games sees the constraint satisfaction problem over \(n\) variables and \(m\) constraints as a constraint graph \(G\) with \(n\) vertices and \(m\) edges, where the edges are labeled by permutations of the alphabet \([Q]\): the goal is then, given query access to the graph, to distinguish between he minimum fraction of constraints violated by any labeling being at most \(\varepsilon\) or at least \(\rho\). This paper considers the question in the adjacency list access model, where the algorithm can where the algorithm has uniform-vertex, degree, and neighbor query access to the graph. The main result is a tester which (in contrast to previous work) makes no structural assumption on the graph, and, for \(\varepsilon = O(\rho^4/\log n)\), solves this tolerant testing question with query complexity $\(\tilde{O}((\sqrt{m} + n/\sqrt{m})\text{poly}(1/\rho))\)$ for constant alphabet size \(Q\).
Optimal Testing of Reed-Muller Codes with an Online Adversary, by Esty Kelman, Uri Meir, Kai Zhe Zheng (arXiv). In the online erasure model of property testing, after each query made to the input \(f\), an adversary gets to erase up to \(t\) (adaptively chosen) values of \(f\). This makes the testing task much more challenging, requiring testers to (intuitively) behave somewhat unpredictably. In this paper, the authors define a new type of testers, in-between sample-based (only make uniformly random queries to the input) and query-based: semi-sample-based testers, which first choose an arbitrary subset \(S\) of potential queries, and then get uniformly random queries from \(S\). The main results are (1) a semi-sample-based tester for Reed-Muller codes in the “usual” testing model, which (2) can be made to work in the online erasure model (complemented by a lower bound showing it is then near-optimal).
Mean Testing under Truncation beyond Gaussian, by Yuhao Wang, Roberto Imbuzeiro Oliveira, Themis Gouleakis (arXiv). In the Mean Testing problem, given i.i.d. samples from a high-dimensional distribution with unknown mean vector \(\mu\), the goal is to distinguish between \(\|\mu\|_2=0\) and \(\|\mu\|_2 > \alpha\). While the fundamental cases of \(d\)-dimensional Gaussian distributions and product Bernoulli distributions are fully understood, a natural generalization is what happens when the samples are corrupted or censored: for instance, if samples are truncated (i.e., only samples within an (unknown) set \(S\) can be observed). Work of Canonne, Gouleakis, Wang, and Yang (2025) addresses the case of mean testing under truncation for identity-covariance Gaussians: this paper significantly generalizes these results, dropping the Gaussianity to allow for any class of high-dimensional distributions satisfying a bounded moment assumption.
Distributed Gaussian Mean Testing under Communication Constraints: messages, samples, and coins, by Clément Canonne and Nimitt (arXiv). Going back to Gaussian mean testing, what happens when the i.i.d. samples are distributed among \(n\) users each holding \(m\) samples, subject to strict (but possibly different) one-way communication constraints, and sharing a small random seed? The authors provide algorithms for Gaussian mean testing in this very general setting, which capture as special cases a number of previous works on distributed mean testing, and allow for smooth trade-offs between the parameters at play.
And now, onto the quantum realm!
On Clifford hierarchy testing and near-extremizers of noncommutative uniformity norms, by Zongbo (Bob) Bao, Jop Briët, Davi Castro-Silva, Philippe van Dordrecht, and Jonas Helsen (arXiv). The Clifford hierarchy is a sequence of quantum circuit models, allowing for increasingly general gates (the first level of the Clifford hirerachy being the set of Pauli gates, and the second is the Clifford group). In this paper, the authors consider the question of testing, given access to a unitary \(U\) (and its inverse), whether it belongs to a given level of the Clifford hierarchy, or is far from it. Their main result is an efficient testing algorithm for the 3rd level of the Clifford hierarchy, the first one still open: to do so, they establish a “robust inverse theorem” for the fourth Pauli uniformity norm \(P^4\), relating the closeness of a unitary to the 3rd level of the Clifford hierarchy to to its \(P^4\) norm.
Practical Tests and Witnesses of Fermionic non-Gaussianity, by Tobias Haug, Xhek Turkeshi, and Piotr Sierant (arXiv). In this paper, the authors are concerned with quantifying and detecting the distance of a (pure) \(n\)-qubit-quantum state to the set of Fermionic Gaussian States (FGS). Among other results, they provide two testing algorithms which distinguish between (1) being a (pure) Fermionic Gaussian state and (2) being at trace distance at least \(\varepsilon\) from every FGS: the first, using \(O(n^2/\varepsilon^2)\) two-copy Bell measurements, and the second, using \(O(n^3/\varepsilon^4)\) single-copy measurements.
Quantum Multi-Level Estimation of Functionals of Discrete Distributions, by Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, Xinzhao Wang (arXiv). Given purified quantum query access to a classical probability distribution \(p\) over \(n\) elements, i.e., access to a unitary which prepares the state $$\sum_{i=1}^n \sqrt{p_i}|i\rangle |\textsf{garbage}_i\rangle$$, the goal is to estimate a functional \(f(p)\) of the distribution: distance to uniformity, entropy, support size… This paper provides a general framework to do so, for any function \(f\) for which \(f^2\) admits a low-degree polynomial approximation. As a direct application, the authors obtain improved quantum algorithms for estimating the \(q\)-Tsallis entropy of a discrete distribution, for all ranges of parameter \($q\) (and near-optimal for \(q > 1\)).
Sticking with distributions, but back to classical…
Entropy Equivalence Testing, by Clément Canonne, Yash Pote, Jonathan Scarlett, and Joy Qiping Yang (arXiv). In the standard task of closeness testing for probability distributions, one gets i.i.d. samples from two unknown probability distributions \(p,q\), and must distinguish between (1) \(p=q\) and (2) \(\text{TV}(p,q) > \varepsilon\), where TV denotes the total variation distance. This is now well-understood — but what happens when one changes (2) to something else? Some previous work considered different notions of distance than TV distance: in this work, (2) is relaxed to a much weaker version, only asking to reject when the entropies of \(p,q\) are significantly different. As shown in the paper, not only does this variant lead to a more sample-efficient tester, it can be very useful: used as a blackbox, this yields a better learning algorithm for a well-studied class of high-dimensional distributions, that of Bayesian networks.
Testing properties of trees in graphical models with covariance queries, by Sofiya Burova, Francisco Calvillo, Gábor Lugosi, Piotr Zwiernik (arXiv). The goal of this paper is to test properties about the structure of high-dimensional distributions (specifically, of Gaussian graphical models), but not from samples: instead, given queries to their covariance matrix, or, equivalently, to the graph encoding dependencies between variables. Here, the assumption is that this underlying graph is a tree, and the goal is to test its diameter: the main result is an bicriteria testing algorithm which decides whether the tree has diameter at least \(D\) or at most \((1-\delta)D\), making \(\tilde{O}(\frac{n^2}{D^2\delta^2})\) covariance queries (where \(n\) is the dimension).