Invariance in Property testing (survey)
by Madhu Sudan.
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.
Finally let me list a few other results in this direction
(though I won't describe them due to lack of time):
- 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 .
- 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  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 .
- 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 .
- Succinct Representation of Codes with Applications to
Testing (with Elena Grigorescu and Tali Kaufmann,
ECCC TR09-043): The paper  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 .
- 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.
- Shapira - STOC 2009
- Kaufman and Wigderson - ICS 2010
- Bhattacharyya, Kopparty, Schoenebeck, Sudan, and Zuckerman -
list of Oded's choices.