Invariance in Property testing (survey)

by Madhu Sudan.

Oded's comments

Madhu mused on what makes problems easily testable and suggested that closure under a rich permutation group plays a major role. This seems supperted by the numerous results regarding algebraic functions (which are all invariant under suitable affine transformation) and graph properties (which, by definition, are closed under isomorphism). He surveyed a unified approach that refers to the former, where the affine transformations refer to the identification of the main with a vector space.

The original abstract

This series of works was triggered by a question/conjecture in a work of Alon, Kaufman, Krivelevich, Litsyn and Ron (AKKLR) who asked if every 2-transitive code with a local constraint was locally testable. On thinking about the question we realized that no one seemed to have explicitly studied the role of invariance of a property when testing it. In retrospect, this property seems to be crucial in (a) defining graph-properties (these are properties that remained unchanged when we renumber the vertices), (b) separating the new (i.e., twentieth century) work in property testing from the classical domain of statistics: Statistics typically deal with properties which enjoy a full symmetry group (names of all participants can be changed and this should not affect the statistics), whereas property testing tries to determine satisfiability of properties which do not enjoy a full symmetry group (e.g., graph properties are not invariant under arbitrary movement of edges), and (c) algebraic properties also have nice (and much smaller) symmetry groups. The AKKLR question/conjecture could be generalized in this sense to asking: When can you take property described by a local forbidden pattern (constraint) and the symmetry group of the property and use them to characterize and test the property? We explored this question in a series of works.
  1. Algebraic Property Testing: The Role of Invariance (with Tali Kaufman, ECCC TR07-111): In this work we considered properties of functions that formed a linear vector space over some field F, where the domain of the functions were of the form K^n where K was a (small) field extending F, and where the property was invariant under linear transformations of K^n. We gave necessary and sufficient conditions for such properties to be testable with constant queries (when K was of constant size). While the motivation for these families were low-degree polynomials, we showed not all properties here were low-degree polynomials and the degree did not characterize the locality of the test. Paper available here [1].
  2. 2-Transitivity is insufficient for Property Testing (with Elena Grigorescu and Tali Kaufmann, ECCC TR08-033): In this work we used some of the functions explored in paper [1] above, but over large fields K, to get a counterexample to the AKKLR conjecture (this clearly shows that affine/linear-invariance is not just syntactic variations on polynomials, which were well0-understood by AKKLR). Paper available here [2].
  3. Testing Linear-Invariant Non-Linear Properties (with Arnab Bhattacharyya, Victor Chen, and Ning Xie, ECCC TR08-088): In this work we explored some properties that were not vector spaces (so functions that were not closed under addition), but still linear invariant. This led to a nice bridge between combinatorial property testing and algebraic property testing. Paper available here [3].
  4. Succinct Representation of Codes with Applications to Testing (with Elena Grigorescu and Tali Kaufmann, ECCC TR09-043): The paper [1] showed that if some properties were characterized by a single local constraint and its rotations under the group of affine transformations, then it was locally testable by the natural test. In this work we showed that many codes, including sparse affine-invariant codes over fields of the form 2^prime have this property. Paper available here [4].
  5. Limits on the rate of locally testable affine-invariant codes (with Eli Ben-Sasson, unpublished): In this work we show that (despite its richness) affine-invariance is not going to lead to much denser locally testable codes than already known. While the result is disappointing, if one cares about property testing beyond just the construction of locally testable codes, then this results adds to the body of knowledge on algebraic property testing.
Finally let me list a few other results in this direction (though I won't describe them due to lack of time):

Back to list of Oded's choices.