In June, we had a property testing workshop at Haifa where a lot of recent PT work was discussed. Check out the post on that. June also saw some interesting developments on testing affine-invariant properties, on testing sub-properties, on local computation algorithms, and on PCP constructions.
TESTING AFFINE-INVARIANT PROPERTIES
Over the last few years, there has been much progress in determining which affine-invariant properties of boolean functions can be tested with a constant number of queries. In Estimating the distance from testable affine-invariant properties (arXiv, ECCC), Hamed Hatami and Shachar Lovett show that for every such property, we can not only test it but also estimate the distance to the property with a constant number of queries.
The function linear isomorphism testing problem asks: How many queries do we need to test if a given (unknown) function is equivalent, up to a linear transformation of the input space, to some (known) function \(f\)? The answer to this question depends on the choice of the function \(f\). Elena Grigorescu, Karl Wimmer, and Ning Xie, in Tight lower bounds for testing linear isomorphism (ECCC) and Abhishek Bhrushundi, in the concurrent and independent paper On testing bent functions (ECCC), show that the query complexity for testing linear isomorphism is maximized when \(f\) is the Inner Product function. Interestingly, the proofs of this result (and other more general results) are obtained using completely different methods: Elena, Karl, and Ning prove their lower bounds using the communication complexity method, while Abhishek’s proof is obtained by studying the parity decision tree complexity of boolean functions.
TESTING SUB-PROPERTIES
One counter-intuitive aspect of property testing is that the query complexity for testing \(P\) does not in general imply anything about the query complexity for testing a sub-property \(P’ \subseteq P\). For example, while we can test halfspaces (aka, linear threshold functions) with a constant number of queries, testing the subclass of signed majorities is known to require \(\Omega(\log n)\) queries, and in fact the best-known algorithm for this task is a non-adaptive tester that requires \(O(\sqrt{n})\) queries. In Exponentially improved algorithms and lower bounds for testing signed majorities (ECCC), Dana Ron and Rocco Servedio dramatically improve both the upper and lower bounds: they show that non-adaptive algorithms for testing signed majorities require \(\mathrm{poly}(n)\) queries and that signed majorities can be tested by an adaptive algorithm that requires only \(\mathrm{polylog}(n)\) queries.
Another phenomenon that appears in some natural properties is that while a property \(P\) requires many queries to test, it can be partitioned into (slightly) smaller properties \(P’\) that can each be tested with a constant number of queries. It is natural to ask whether this is a universal phenomenon. In Some properties are not even partially testable (arXiv, ECCC), Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish show that it is not: they show that there are properties \(P\) for which every (large enough) sub-property of \(P\) requires a large number of queries to test.
LOCAL COMPUTATION AND PCP CONSTRUCTIONS
A notion that is very closely related to property testing is that of local computation
algorithms: algorithms that, as in the property testing setting, aim to compute the solution of a problem in sublinear time by querying as few bits of the input as possible. In A Local Computation Approximation Scheme to Maximum Matching (arXiv), Yishay Mansour and Shai Vardi give a new local computation algorithm for obtaining a \((1-\epsilon)\)-approximation to the maximum matching in bounded-degree graphs.
The notion of Probabilistically Checkable Proofs (PCPs) is also closely related to property testing, where now the input to the tester is a string \(x\) and a purported proof that \(x\) satisfies some property \(P\); the tester must verify the correctness of the proof while examining as few bits of \(x\) and of the proof as possible. A long-standing open problem in this area is to understand the best possible trade-offs between the query complexity and the length of proofs for PCP constructions. In Constant rate PCPs for circuit-SAT with sublinear query complexity (ECCC), Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth give a verifier for a special case of PCPs that obtains a sublinear query complexity with proofs that have length only linear in the size of the input.