TR07-111 Authors: Tali Kaufman, Madhu Sudan

Publication: 2nd November 2007 00:41

Downloads: 2891

Keywords:

We argue that the symmetries of a property being tested play a

central role in property testing. We support this assertion in the

context of algebraic functions, by examining properties of functions

mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$.

We consider $\F$-linear properties that are invariant under linear

transformations of the domain and prove that an $O(1)$-local

``characterization'' is a necessary and sufficient condition for

$O(1)$-local testability when $|\K| = O(1)$. (A local

characterization of a property is a definition of a property in

terms of local constraints satisfied by functions exhibiting a

property.) For the subclass of properties that are invariant under

affine transformations of the domain, we prove that the existence of

a {\em single} $O(1)$-local constraint implies $O(1)$-local

testability. These results generalize and extend the class of

algebraic properties, most notably linearity and low-degree-ness,

that were previously known to be testable. In particular, the

extensions include properties satisfied by functions of degree

linear in $n$ that turn out to be $O(1)$-locally testable.

Our results are proved by introducing a new notion that we term

``formal characterizations''. Roughly this corresponds to

characterizations that are given by a single local constraint and

its permutations under linear transformations of the domain. Our

main testing result shows that local formal characterizations

essentially imply local testability. We then investigate properties

that are linear-invariant and attempt to understand their local

formal characterizability. Our results here give coarse upper and

lower bounds on the locality of constraints and characterizations

for linear-invariant properties in terms of some structural

parameters of the property we introduce. The lower bounds rule out

any characterization, while the upper bounds give formal

characterizations. Combining the two gives a test for all

linear-invariant properties with local characterizations.

We believe that invariance of properties is a

very interesting notion to study in the context

of property testing, in general and merits a systematic study.

In particular, the class of linear-invariant and affine-invariant

properties exhibits a rich variety among algebraic properties and

offer better intuition about algebraic properties than the more

limited class of low-degree functions.