Happy new year, everyone! Last year ended with a bang, featuring no fewer than 11 papers on property testing! As usual, if we forgot any, please let us know in the comments.

We’ll start with graphs, then move to locally testable and decodable codes, turn to quantum computing, make a stop around neural networks, and finally head towards probability distribution testing. Just as 2025 was, it’s a journey!

Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size, by Debarshi Chanda (arXiv). (Technically from November, but which we missed at the time). Given access to an unknown undirected graph, efficiently estimating its number of edges \(m\) is arguably a very fundamental (and well-studied) question. Recent work has provided sublinear-query algorithms which only require access to “degree”, “neighbour”, and “random edge” queries. However, previous algorithms did require a priori knowledge of some of the graph parameters — such as its number of vertices \(n\). This paper’s main contribution is an algorithm which only makes “degree” and “random edge” queries, does not require knowledge of any of the graph parameters, and outputs an \(1\pm \varepsilon\) multiplicative estimate of its number of edges with an expected \(\tilde{O}(\alpha n/(\varepsilon^2 m)\) queries, where \(\alpha\) is the (unknown) arboricity of the graph. Further, the author shows that allowing a wider range of query types cannot lead to significantly more efficient algorithms.

Optimal non-adaptive algorithm for edge estimation, by Arijit Bishnu, Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, and Gopinath Mishra (arXiv). Very related to the previous paper, this one does assume knowledge of the number of vertices \(n\), and parameterizes the complexity of the algorithm as a function of \(n,m\) only (bot the arboricity \(\alpha\). The key focus and difference, however, is that the algorithm is non-adaptive, in contrast to all previous algorithms for the task, achieving an expected \(\tilde{O}(\sqrt{n}/\varepsilon^{2.5})\) query complexity with only “degree” and “random edge” queries (to be compared with the adaptive query complexity in this query model, recently shown to be \(\tilde{O}(n^{1/3})\) by Beretta, Chakrabarty, and Seshadhri).

Graph Limits via Quotients, by Eitan Levin and Venkat Chandrasekaran (arXiv). To quote the abstract, this paper introduces “a new notion of limits of weighted directed graphs of growing size based on convergence of their random quotients.” These limits, that the authors name grapheurs, are meant to better capture global structures and “hub” behavior, in contrast to other type of graph limits such as graphons. Along with defining and analyzing their new notion, the authors derive an “edge-based analogue” of Szemerédi’s regularity lemma for grapheurs, and leverage it in Section 4 to obtain an edge-based sampling property tester for hubs (Example 4.11).

Good Locally Testable Codes with Small Alphabet and Small Query Size, by Uriya First and Stav Lazarovici (arXiv). A good code is an error-correcting code with both (relative) distance and rate \(\Omega(1)\). A \(q\)-query locally testable code (LTC) is a code which admits a tester (here assumed to be non-adaptive) making \(q\) queries to strings to test whether they are valid codewords. The existence of good LTCs was established independently in 2022 (for large values of \(q\)) by inur–Evra–Livne–Lubotzky–Mozes and Panteleev–Kalachev; First and Kaufman (2024) then showed good 2-query LTCs (but on large alphabets). Several impossibility results, under conditions on \(q\) and alphabet size, were known, but a characterization was unclear: untile now, as this paper settles which values of \(q\) and alphabet size admit good LTCs.

3-Query RLDCs are Strictly Stronger than 3-Query LDCs, by Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng (arXiv). A \(q\)-query locally decodable code (LDC) is an error-correcting code such that any given bit of a message can be decoded by only querying \(q\) bits of the (possibly corrupted) codeword. A relaxed LDC (RLDC) is nearly the same, except for the fact that the decoder can give up (output \(\bot\)) on a small fraction of corrupted codewords (i.e., it only needs to be able to decode most of the bits of most of the slightly-corrupted codewords). While the existence of 2-query LDCs with rate \(o(1/n^3)\) had recently been shown to be impossible, this paper showed that 2-query RLDCs with rate \(\tilde{\Omega}(1/n^2)\) do exist, showing a strict separation between relaxed and usual (stressed out?) LDCs.

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting, by
Kean Chen, Qisheng Wang, and Zhicheng Zhang (arXiv). The quantum sample-to-query lifting framework, introduced by Wang and Zhang in 2025 and strengthened by Tang, Wright, and Zhandry the same year, enables one to (as the name suggests) lift sample complexity lower bounds to query complexity, and as a result to, for instance, prove lower bound for property testing in the quantum setting. This paper applies this framework to a wide range of tasks, obtaining improved bounds (or re-deriving new bounds) for what can only be called a pretty big number of quantum testing problems, both for classical properties and quantum ones.

A random purification channel for arbitrary symmetries with applications to fermions and bosons, by Michael Walter and Freek Witteveen (arXiv). In this paper, the authors introduce a generalization of the random purification channel (whereby an arbitrary mixed state is (randomly) cast as a pure state in a larger space, often simplifying the task at hand) to general symmetry groups or algebras. While this is a little over my head, an application of the above is in learning (tomography) and testing quantum states: namely, the paper provides improved upper bound for testing whether an arbitrary pure state is a whether a pure state is a fermionic Gaussian state (Corollary 1.6).

Optimal certification of constant-local Hamiltonians, by Junseo Lee and Myeongjin Shin (arXiv). Last May, we covered two papers on Hamiltonian testing, one about tolerant certification (the quantum analogue of classical (distribution) identity testing), and the other about locality testing (i.e., whether a Hamiltonian can be decomposed as the sum of simple operators). In this paper, the authors consider the (non-tolerant) version of certification, under the assumption that the Hamiltonian is local: and obtain optimal query complexity for the case where it is \(O(1)\)-local. Now, the twist, and in contrast to the first paper from May mentioned above, here the algorithm is only allowed to query the the evolution operator \(e^{-iH t}\) of the Hamiltonian \(H\) in the forward time direction (no “rewinding”!), a more stringent query access model.

Going back to classical computing, the testing continues!

Property Testing of Computational Networks, by Artur Czumaj and Christian Sohler (arXiv). This paper initiates the study of computational networks (that is, neural networks) from the testing point of view. While one could think this is just standard property testing—after all, a neural network computes a function, and testing functions has been considered before! the authors make the case that the implementation of the function as a network is the key aspect here. The framework they define and introduce for this (with, as leading example, the case of ReLU networks) thus focuses on the device computing the function, and the notion of distance used is very much reliant on this: that is, the measure of distance is the fraction \(\varepsilon\) of weights of the networks that need to be modified in order to make the function it computes \(\delta\)-close to the property.

A Distribution Testing Approach to Clustering Distributions, by Gunjan Kumar, Yash Pote, and Jonathan Scarlett (arXiv). Here, the authors consider an (arguable very natural) task: given \(k\) discrete distributions available through sample access, and a parameter \(\varepsilon\), how to recover a hidden partition in two sets such that (1) every distribution within a given set are identical, and (2) the distributions of the two sets are \(\varepsilon\)-far in total variation distance? While previous work on this focuses on asymptotic guarantees, this paper builds on techniques from distribution testing to obtain finite-sample upper and nearly-matching lower bounds, considering both the setting where one of the two distributions is known, and that where both distributions are unknown. The paper concludes with three open problems and future directions, so… worth having a look!

Instance Dependent Testing of Samplers using Interval Conditioning, by Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, and Sayantan Sen (arXiv). To conclude this month’s post, a distribution testing paper focusing on infinite domains, and instance-optimal guarantees. Motivating their work from the viewpoint of verifying GenAI/probabilistic AI output distributions, the authors consider the question of identity testing over discrete but infinite domains (such as \(\mathbb{Z}\)), parameterized by a relevant “smoothness” parameter, the “tilt”, involving both the known and unknown distributions. To enable more efficient testing, the algorithms are allowed a stronger type of sampling that i.i.d. sampling, namely, the interval conditional sampling access of Canonne-Ron-Servedio (2015), which lets one sample from a distribution conditioned on any interval of one’s choosing. Finally, to complement their theoretical analysis, the authors provide an empirical evaluation of their algorithm.

Edit: two more papers, that we had missed from last month!

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries, by Yumou Fei (arXiv). This paper shows strong lower bounds in the bounded-degree query model, for graph testing: namely, that testing satisfiability requires \(\Omega(n)\) queries for the entire class of unbounded-width CSPs. Put differently, all CSPs known to be NP-hard are also maximally hard to test in the bounded-degree model!

A Dichotomy Theorem for Multi-Pass Streaming CSPs, by Yumou Fei, Dor Minzer and Shuo Wang (arXiv). In this paper, the authors show a dichotomy theorem on the space needed by multipass streaming algorithms to approximate CSPs. While focusing on streaming algorithms, this paper discusses connections to property testing (Section 1.2.2), specifically to the bounded-degree model for graph testing.