The latest in property testing and sublinear time algorithms
Last month saw seven papers covering a reasonable range of topics in property testing. Our line up contains diversions in distribution testing, graph property testing and quantum. Let us start with a result from the quantum land on spectrum estimation. (And oh, let me add that all em-dashes in this post are human generated). Spectrum […]
Our press release this month features five papers: four of them are squarely property testing papers, and a fifth which I could not, in good conscience, bring myself to omit. Let us take a look: a paper that carries the submodularity testing story from two labels up to \(k\) of them; a striking super-polynomial quantum […]
The 10th edition of WoLA, the Workshop on Local Algorithms, will be taking place on August 16-18, 2026 at at Boston University, Boston, MA, just before APPROX/RANDOM! For those unfamiliar with WoLA: Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have […]
10 11 12 papers in May! With a mix of testing for logic, quantum, codes, and distribution testing, this was a very prolific and well-rounded month. Let’s get to it, in no particular order! Constant time testability of first-order logic with modulo counting on finitary graphs, by Isolde Adler, Jenny Stimpson (arXiv). This paper is […]
Apologies for the major delay! We have a nice bounty of 8 papers, with a big haul of graph property testing papers. Let us not delay even further and get right to it. Sublinear-query relative-error testing of halfspaces by Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, and Tianqi Yang (arXiv). This […]
After either really busy months or really quiet months, we’re now on a moderately busy month (which is the way it should be). A collection of 7 papers, now showing an increased interest in sublinear graph algorithms. Of course, we still have some distribution testing, and a paper on sparse functional representations. A note on […]
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 […]
After some insanely busy months, we have a merely busy month. A couple of neat results on sublinear graph algorithms (a subject dear to me!), DNF testing, and two expositions that should be of interest to our readers. When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries by Tomer Adar, […]
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 […]
Last month the community had a lot to say as a result of which we have a rare treat featuring eighteen papers. Results ranging from (almost) tight lower bounds for testing boolean monotonicity to low rank approximation of Hankel Matrices, to compressed sensing, to PCPs, to results about testing and learning convex functions, a trio […]