We saw two new property testing papers in October. During the month, we also saw a great presentation on estimating the distance to testable affine-invariant properties (discussed here) at FOCS, and we saw some intriguing property testing papers in the list of accepted papers for ITCS 2014.

Survey on Quantum Property Testing by Ashley Montanaro and Ronald de Wolf (arxiv). We already mentioned this survey here, but it is worth discussing it again. With a clear presentation of fundamental results in the area, this survey is a great reference for any researcher in property testing or in quantum complexity that wants to learn about the intersection of the two fields. And with 12 open questions presented throughout the text, this is also the ideal starting point for any researcher who wants to jump into the area.

Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees by Abhishek Bhrushundi, Sourav Chakraborty, and Raghav Kulkarni (ECCC). The authors observe that the problem of testing a property \(P\) of linear or quadratic boolean functions is equivalent to determining the parity decision tree complexity of a function \(f\) determined by \(P\). This connection is used to obtain strong lower bounds on the query complexity required to test \(k\)-linearity, bent functions, and other related properties. It also provides further motivation for the the study of parity decision trees and the related problems on the Fourier structure of boolean functions.