Dear PTReview readers, we are in the brave new world of LLM assisted math papers. The total number of papers we need to look through each month has almost tripled, so apologies if your paper get missed. Please email little.oh.of.n@gmail.com with a link to an arXiv or ECCC paper. In general, we would appreciate sending us such an email as soon as your paper gets public, to make it easier for the editors to keep track of property testing papers.
We have a large collection of eleven (!!) papers, which we arrange by subtopic.
Query Complexity of Testing Structured Parenthesis Languages by Tim Jackman, Diptaksho Palit, and Sofya Raskhodnikova (arXiv). This paper and the next study the classic problem of testing Dyck languages, which are formed by correct parenthetical strings. When there is only one parenthesis type, then there are \(O(poly(1/\varepsilon))\) query property testers. When there are two or more parentheses types, the complexity jumps to somewhere between \(\Omega(n^{1/5})\) and \(O(n^{2/5+\delta})\). This paper proves an (almost) optimal lower bound of \(\Omega(n^{2/5})\), even for adaptive algorithms. A non-adaptive lower bound of \(\Omega(n^{1/2})\) is also proven. In addition, the paper proves that complexity is \(\Theta(\varepsilon^{-2})\) for single parenthesis type setting.
Near-Optimal Bounds for Testing Residual-String Equality and Parenthesis Languages by Hadar Strauss (arXiv). The primary result of this paper is the same: the adaptive \(\Omega(n^{2/5})\) and non-adaptive \(\Omega(\sqrt{n})\) lower bounds. This paper also shows a non-adaptive upper bound of \(O(n^{1/2+\delta})\) (for any \(\delta > 0\)), and gives an improved dependence on \(\delta\) for the adaptive setting. The lower bound constructions in both papers go via a “hidden” or “residual” string equality problem, wherein binary strings are padded with a dummy \(*\) symbol. The aim is to determine properties of the binary string after the dummy symbols are removed.
Collision Detection is Instance \(\widetilde{O}\)ptimal Under the Birthday Threshold by Omri Ben-Eliezer, Tomer Grossman, Václav Rozhoň, and Jakub Tětek (arXiv). Consider the classic problem of collision detection in a function \(f:[n] \to [n]\). So we want to find \(x \neq y\) such that \(f(x) = f(y)\). As our readers will likely know, if \(f\) is random, a standard birthday paradox argument shows that \(O(\sqrt{n})\) samples suffice. Suppose we knew something about the function \(f\), such as the structural properties of \(f\): then it is quite plausible we can beat the birthday paradox bound. This paper shows there is an instance optimal algorithm that is \(O(\log n)\)-competitive. This means, even if we design a tailormade algorithm that is optimized for a specific \(f\), the algorithm of this paper will take at most \(O(\log n)\) factor more queries. It is also known that this overhead cannot be beaten.
Testing the Binary Rank with Polynomial Query Complexity by Michal Parnas (arXiv). Consider an \(n \times m\) Boolean matrix \(M\). The binary rank is the smallest \(d\) such that \(M = AB\), where \(A, B\) are Boolean matrices. And \(A\) has dimension \(n \times d\), and \(B\) has dimension \(d \times m\). The multiplication is done over the integers (not over \(\mathbb{F}_2\), which would correspond to the Boolean rank). This paper studies the property testing version, where distance is naturally measure by (fractional) Hamming weight. The main result is an adaptive two-sided property testing, with query complexity \(\widetilde{O}(d^3/\varepsilon^2)\). Previous results have query complexities exponential in \(d\).
Testing Bipartite in the Bounded-Degree Graph Model, Revisited (A digest of the paper of Fei and Rubinfeld (2026)) by Oded Goldreich (ECCC). As the title says, this paper is an exposition of a recent Fei and Rubinfeld on a simpler analysis of the classic bipartiteness tester for Goldreich-Ron. It lays out the key differences of the Fei-Rubinfeld result, and gives an accessible explanation of the main ideas.
Private Graph Property Testing by Hendrik Fichtenberger, Abigail Gentle, Tamalika Mukherjee, Sayantan Sen (arXiv). Differential privacy (DP) and property testing have a lot in common. At its heart, DP is about the sensitivity of algorithms to their input. It feels like property testers should be differentially private, since they make inferences on the input by only sampling a small portion of the input. This paper makes the connections rigorous for graph property testing. For graph inputs, there are various notions of DP, called edge-DP and node-DP (depending on whether we want to preserve the privacy of node existence or edge existence). The paper provides a nice framework that connects graph property testers with DP. One of the main results, using canonical property testers for dense graphs, gives edge-DP and node-DP property testers for any property. The private query complexity is only a constant factor more than the non-private canonical tester. For bounded degree graphs, the paper gives a private version of the classic bipartiteness tester, using privacy preserving random walks. There are also results for hyperfinite graph properties.
On the Power of Adaptivity in Testing Quantum States in Fidelity by Jan Seyfried, Sayantan Sen, Marco Tomamichel (arXiv). This paper is on testing of quantum states, a topic that has seen much research over the past couple of years. This problem is the quantum equivalent of distribution testing: consider a known quantum state \(\sigma\). Given input to an unknown quantum state \(\rho\), we wish to distinguish \(\rho = \sigma\) from \(\rho\) being far from \(\sigma\). Typical results measure distance in terms of a trace norm, but this paper focuses on an alternate distance notion called fidelity. For the original trace norm distance, various problems (certification, equivalence, and independence) all have basically the same complexity of \(\widetilde{\Theta}(d^{3/2}/\varepsilon^2)\), where \(d\) is the dimension of the quantum states. It was known that adaptivity does not help. For fidelity, the bounds change for the various problems, and adaptivity does give a provable improvement for equivalence and independence testing.
Distributed Quantum Property Testing with Quantum Carrier Pigeons by Kenny Chen, Mina Doosti, Ryan Sweke, Chirag Wadhwa (arXiv). This paper studies the same problem of quantum state testing, but in a distributed setting. Imagine that there are multiple nodes (called distributed nodes) that carry copies of the quantum state to be tested. They all communicate with a central node that has to solve the inference task. This model is inspired by a classic version of distributed distribution testing. There is a limit of classical bits (\(n_c\)) and qubits (\(n_q\)) that can be sent from each distributed node to the central node. When \(n_q\) is larger than the number of qubits in the quantum state, the entire state can be sent to central node. The interesting case is when \(n_q\) is smaller. This paper shows that with public randomness, there are non-trivial distributed algorithms, but there are lower bounds for private randomness.
Optimal Quantum State Testing Even with Limited Entanglement by Chirag Wadhwa, Sitan Chen (arXiv). Another paper on quantum state testing, but looking at the power of entanglement. The testing algorithms need to be multiple copies (or samples) of the input quantum state. But in previous optimal algorithms, these have to be entangled, which allows for a copy complexity \(\widetilde{O}(d/\varepsilon^2)\). Without any entanglement, the complexity jumps by a quadratic factor. This paper studies what happens if the entanglement is limited to \(t\). The complexity achieved is (essentially) \(\widetilde{O}(d^2/\sqrt{t}\varepsilon^2)\), giving a smooth tradeoff between the extreme cases.
Good Quantum Locally Testable Codes from Product Expansion by Mitali Bafna, Anqi Li, and Quynh T. Nguyen (arXiv, ECCC). A locally testable code (LTC) is one for which the property of codewords has a constant query property tester. The tester is defined by a collection parity checks over subsets. A constant number of these checks are sampled uniformly at random to get the property tester. This paper shows that, assuming a conjecture about product expansion of Reed-Solomon codes over binary extension fields, there are quantum LTCs with constant rate, distance, soundness and locality.
Streaming Hypergraph Coloring via Palette Sparsification by Artur Czumaj, Pan Peng, Ruizhe Shi, Christian Sohler (arXiv). Formally, this is not a property testing paper, but palette sparsification is a fundamental tool in sublinear algorithms. So this is a good paper for our readers to check out. Let us leave aside the actual streaming results (which are interesting!). Palette sparsification is a technique where each vertex gets a subset of randomly sampled colors. One proves that there is a legal coloring where each vertex only picks from its “local palette”. This was a critical tool in sublinear graph coloring algorithms, and this paper generalizes the tool for hypergraphs. For coloring hypergraphs, we only need that no edge is monochromatic. One can prove that \(\Theta(\Delta^{1/(k-1)})\) colors suffice for a proper coloring, where \(\Delta\) is the maximum degree and all hyperedges have arity \(k\). The main theorem shows that \(\Theta(\sqrt{\log n})\) length lists suffice for each vertex.