SODA 2014 had a bunch of property testing papers, all but one of which have been covered by our monthly reports. (This, arguably, shows that the monthly reports have some value.) I’ll just give the list of papers, and only give a summary for the “new” papers.

Testing equivalence between distributions using conditional samples by Clément Canonne, Dana Ron and Rocco A. Servedio

Optimal Algorithms for Testing Closeness of Discrete Distributions by Siu On Chan, Ilias Diakonikolas, Gregory Valiant and Paul Valiant

Testing Surface Area by Chenggang Wu, Ryan O’Donnell, Amir Nayyeri, and Pravesh Kothari

Hereditary properties of permutations are strongly testable by Tereza Klimosova and Daniel Kral (Arxiv). This papers solves an important open problem in permutation testing, and shows that all hereditary properties of permutations are testable, when the distance is given by the Kendall-Tau metric. Such a result was already known for the rectangular metric. The Kendall-Tau metric is the right analogue to the standard edit distance for graph properties, and so this result becomes the analogue of testing of hereditary graph properties.