Apologies for the very late post! Last month was a bit calmer on the property testing front, with “merely” 3 papers we found. (Of course, if we missed any… let us know in the comments!)

Testing Monotonicity of Real-Valued Functions on DAGs, by Yuichi Yoshida (arXiv). Monotonicity of functions is a fundamental, and well-studied property in the literature, and testing monotonicity on the line, the reals, the Bollean hypercube, and the hypergrid (among others) have been studied at great lengths (and yet, still not fully understood!). This paper considers a new twist on the question, where the object of study is a real-valued function defined on an \(n\)-vertex directed acyclic graph (DAG) provided to the algorithm. The key contribution of this work is showing that, on this type of structured poset, testing monotonicity requires \(\Omega(n^{1/2-\delta}/\sqrt{\varepsilon})\) non-adaptive queries for any constant $\delta>0$, nearly matching the general-poset non-adaptive upper bound of Fisher, Lehman, Newman, Raskhodnikova, Rubinfeld, and Samorodnitsky (2002). The paper also provides a similar adaptive lower bound, for one-sided testers. The author also establishes more fine-grained results (both upper and lower bounds), leveraging assumptions on either the range of the function, or the sparsity of the DAG.

The Power of Two Bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements, by Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu (arXiv). Following recent works by Huang, Preskill, and Soleimanifar, and then Gupta, He, and O’Donnell, this paper considers the task of state certification (“is this unknown quantum state, which I am given copies of, equal, or very different from, the reference quantum state I want?”), which can be seen as the quantum analogue of identity testing in the classical distribution testing case, for pure reference target states. The key aspect of these works is that one requires the testing algorithm to make very “simple” (ideally single-qubit ones) on the copies of the unknwon \(n\)-qubit state: the underlying idea being that certifying a state given to you should be, in a very quantifiable sense, much “simpler” than preparing the reference state from scratch, otherwise the whole endeavor is sort of useless. Long story short, in this paper, the authors obtain both a very long title and a much more robust algorithm to perform this task, allowing to do tolerant state certification, with constant tolerance parameter. Only slight wrinkles: the algorithm requires one final measurement on logarithmically many qubits (not a single qubit, which would be the Holy Qugrail), and only works for “nearly all” reference states.

Instance-optimal estimation of \(L_2\)-norm, by Tomer Adar (arXiv). Given i.i.d. samples from an probability distribution \(p\) over an arbitrary discrete domain, estimate its collision probability \(\|p\|^2_2\) (equivalently, its \(\ell_2\)-norm) to a multiplicative \(1\pm \varepsilon\) factor. How hard can this be? Quite surprisingly, this question was not, in fact fully solved, and shows a much more complex landscape than expected, in that the right answer is not the obvious guess. An algorithm matching a (known, yet unpublished) lower bound of Tugkan Batu and myself was posed as an open problem by Tugkan at WoLA 2025: in this work, the author solves the problem, showing that the lower bound is indeed tight, by providing an algorithm achieving the right sample complexity, \(O\left(\frac{1}{\varepsilon \|p\|_2}+\frac{\|p\|_3^3-\|p\|_2^4}{ \varepsilon^2\|p\|_2^4}\right)\). It feels good to see this very simple-looking (but not simple, it turns out!), fundamental question solved.