News for May 2025

Apologies for the delay in publishing this digest. May has seen a lot of activity in property testing, with quite a lot from the quantum side: 8 papers in total! Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers (arXiv) by Kean Chen and Qisheng Wang. Say you have access to […]

News for April 2025

The bonanza of property testing results continues this month, with seven new papers on the arXiv! And with range, too: from regular languages to quantum states, with detours through distribution testing, Boolean functions, and relative error property testing. Oh, and yes, also, (quantum) magic! The Trichotomy of Regular Property Testing (arXiv), by Gabriel Bathie, Nathanaël […]

News for April 2024

We have seven papers for you this month. Our potpourri includes two papers apiece on each of the following themes: Distribution Testing, property testing with a quantum twist, graph property testing, and finally two papers on testing function properties. A featured paper this month covers progress on optimal non-adaptive junta testers. Without further ado, let’s […]

News for September 2023

Sorry for delay in getting this month’s post out. This time we had seven (EDIT) eight (LATER EDIT) nine papers. Thanks to our readers for pointing out a paper we missed. Do let us know if we missed any (EDIT) others. Alright, without further delay, let us look at this month’s spread. Mildly Exponential Lower […]

News for July 2023

We’re now back to our regular cadence of 4+ monthly papers on property testing and sublinear time algorithms. July brings us a new sublinear PageRank computation and numerous results on our trending topics of distribution and monotonicity testing. Without further delay, let’s see the July spread. Estimating Single-Node PageRank in \(\widetilde{O}(\min(d_t,\sqrt{m}))\) Time by Hanzhi Wang and Zhewei […]

News for April 2023

After an empty month, the engines of PTReview are roaring back to life with a fresh batch of papers for this month’s edition. In total, we have four papers that are sure to pique your interest. It’s been an action-packed month with a diverse range of topics covered in the featured papers. The first paper […]

News for January 2021

The first month of 2021 has brought with it 5 papers, covering graph testing, Boolean function testing, and distribution testing — as well as database theory. Let’s dive into it. Random walks and forbidden minors III: \(\mathrm{poly}(d/\varepsilon)\)-time partition oracles for minor-free graph classes, by Akash Kumar, C. Seshadhri, and Andrew Stolman (arXiv). Minor-closed bounded-degree graphs […]

News for April 2020

April is now behind us, and we hope you and your families are all staying safe and healthy. We saw six seven property papers appear online last month, so at least there is some reading ahead of us! A mixture of privacy, quantum, high-dimensional distributions, and juntas (juntæ?). A lot of distribution testing, overall. Connecting […]

News for November 2019

We hit the mother-lode of property testing papers this month. Stick with us, as we cover 10 (!) papers that appeared online in November. EDIT: We actually have 11 papers, check out Optimal Adaptive Detection of Monotone Patterns at the bottom. Testing noisy linear functions for sparsity, by Xue Chen, Anindya De, and Rocco A. […]

News for April 2019

After a quite slow month of March, things sped up quite significantly in April: six different papers, ranging from graph testing to function testing to quantum distribution testing! Update (05/04): We missed one. Seven! Junta correlation is testable, by Anindya De, Elchanan Mossel, and Joe Neeman (arXiv). Junta testing really has seen a lot of […]