From Posts of the Property Testing Review (Nov'25-Mar'26)

This is indeed an unusual entry (on my choices).

Oded's summary

One way of being informed on what is going on in property testing and related areas is to look at the monthly news of the Property Testing Review. Unfortunately, I often forget to do this, and there is no easy way to get reminders (because, unlike ECCC, they don't send announcements on news posts). Consequently, my main source of information regarding new research developements is ECCC, albeit it only covers complexity-oriented developements.

Anyhow, searching for something else today, I got to the Nov'25 News, and was embarassed to see a few entries that I should have recommended (in my choices). As a panance, I decided to go over the news of the last five months and make some laconic comments here. (Works that were already featured on my choices are not included; unsurprisingly, the latter were posted on ECCC.)

• Boolean function monotonicity testing requires (almost) $n^1/2$ queries by Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell [Nov'25 News]
  This work finally settles, approximately, the query complexity of (general (i.e., adaptive two-sided error)) testing monotonicity. The lower bound is $n^c$, for every constant $c$ smaller than $1/2$, and it approximately matches the upper bound of $\tildeO(n^{1/2}$, which is ontained by a non-adaptive tester of one-sided error.
• Unbounded-width CSPs are Untestable in a Sublinear Number of Queries by Yumou Fei [Dec'25 News]
  The notion of bounded-width is not that clear; basically, it is defined (in Apdx A, following FV96) as being solvable by a specific (natural) polynomial-time algorithm. The title neglect to mention that the result refers to a bounded-degree model of CSPs, where each instance contains $O(1)$ occurqances of each variable. In the case of binary (resp., $\ell$-ary) constraints, bounded-degree CSPs correspond to bounded-degree graphs (resp.,. $\ell$-uniform hypergraphs). One corollary of the general result is that, for every $(k,\ell)\neq(2,2)$, testing $k$-colorable $\ell$-uniform hypergraphs requires a linear number of queries. More generally, it assert this lower bound for all CSPs that are NP-hard to solve.
• When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries by Tomer Adar, Yahel Hotam, and Amit Levi [Jan'26 News]
  The point is that in two different query models, a natural problem has complexity $C$, whereas in a model that allows both query-types the complexity is $\sqrt C$. The models, which refer to general graphs, are of (1) neighbor queries, and (2) indepedent-set queries. The complexity of estimating the average degree in each model is essentially $n/\sqrt m$, where $n$ is the number of vertices and $m$ is the number of edges.
• DNF formulas are efficiently testable with relative error by Xi Chen, William Pires, Toniann Pitassi, and Rocco Servedio [Jan'26 News]
  I wish to highlight the (relatively new) model for testing Boolean functions, which was introduced by a related set of authors in Relative-error monotonicity testing. This model, akin to the general graph model (see Chap 10 in my Introduction to Property Testing), considers the relative symmetric difference between the preimages of 1. That is, $f$ is at relative distance at most $\eps$ from $g$ if the symmetric difference between $f^{-1}(1)$ and $g^{-1}(1)$ is at most $\eps\cdot\max(|f^{-1}(1)|,|g^{-1}(1)|)$. Lastly, when testing $f$, one may get random elements in $f^{-1}(1)$ (in addition to the value of $f$ on any query of its choice). (Of course, the tester is charged for these samples as well as for its queries.)
• Mathematical and computational perspectives on the Boolean and binary rank and their relation to the real rank by Michal Parnas [Jan'26 News]
  Section 7.3 of this broad survey discusses property testing of Boolean rank.
• Testing Monotonicity of Real-Valued Functions on DAGs by Yuichi Yoshida [Feb'26 News]
  This paper provides an almost $\sqrt n$ lower bound on the query complexity of (non-adaptive, two-sided error) tester of monotonicity of real functions defined over some fixed $n$-vertex poset. This almost matches the known upper bound, which was obtained by a non-adaptive one-sided tester.
• A note on approximating the average degree of bounded arboricity graphs by Talya Eden and C. Seshadhri [Mar'26 News]
  I have not been following this line of works, so let me extract from the original abstract.
  Estimating the average degree of graph is a classic problem in sublinear graph algorithm. A simple algorithm for this problem, whose running time depended on the graph arboricity, was provided by Eden, Ron, and Seshadhri (2017, 2019), but the underlying simplicity and associated analysis were only implicit in the main result. The current note provides a explicit and clear presentation of the algorithm and its analysis, while avoiding the loss of logarithmic factors (which were due to parameter searches).