Three papers this month close out Summer 2018. Test without Trust: Optimal Locally Private Distribution Testing, by Jayadev Acharya, Clément L. Canonne, Cody Freitag, and Himanshu Tyagi (arXiv). This work studies distribution testing in the local privacy model. While private distribution testing has recently been studied, requiring that the algorithm’s output is differentially private with […]
The summer gets off to a flying start, with three property testing papers, spanning differential privacy, distribution testing, and juntas in Gaussian space! On closeness to \(k\)-wise uniformity, by Ryan O’Donnell and Yu Zhao (arXiv) In this paper, the authors consider the following structural question about probability distributions over the Boolean hypercube \(\{-1,1\}^n\): ” what […]
Six papers for May, including new models, hierarchy theorems, separation results, resolution of conjectures, and a lot more fun stuff. A lot of things to read this month! Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs, by Amit Levi and Erik Waingarten (ECCC). This paper proves a number of new lower […]
February had a flurry of conference deadlines, and they seem to have produced six papers for us to enjoy, including three on estimating symmetric properties of distributions. Locally Private Hypothesis Testing, by Or Sheffet (arXiv). We now have a very mature understanding of the sample complexity of distributional identity testing — given samples from a […]
April was a busy month for property testing. A mixture of distribution testing, junta testing, Fourier transforms, matrix problems, and graph testing. Let’s go! (Update: thanks to Omri Ben Eliezer for correcting some errors in our post. Also, he pointed out that we missed posting about by a property testing paper by Gishboliner-Shapira that appeared […]
November was quite eventful for property testing, with six exciting new results for you to peruse. Alice and Bob Show Distribution Testing Lower Bounds (They don’t talk to each other anymore.), by Eric Blais, Clément L. Canonne, and Tom Gur (ECCC). The authors examine distribution testing lower bounds through the lens of communication complexity, a-la […]
The past years have witnessed a great deal of activity in the field of distribution testing— so much, in fact, that it has become a bit of a challenge to even keep track of what’s happening and what has already happened. While this blog post is not going to be a comprehensive (comprehensible, maybe?) survey or […]
After a few slow months, property testing is back with a bang! This month we have a wide range on results ranging from classic problems like junta testing to new models of property testing. Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism, by Eric Blais, Clément L. Canonne, Talya Eden, Amit […]
(A guest post by Ashley Montanaro on quantum property testing, a blogpost on his survey. Thanks Ashley!) Quantum property testing As readers of this blog will be aware, the field of property testing is a vibrant and active area of research, with hundreds of papers having been written covering a vast range of topics. One […]
Helly-Type Theorems in Property Testing by Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, and Shubhangi Saraf (arXiv). Helly’s Theorem states that if every \(d+1\) sets in a family \(F\) of convex sets in \(\mathbb{R}^d\) have non-empty intersection, then the intersection of the whole family \(F\) is also non-empty. This paper establishes a new connection between Helly’s theorem and clustering […]