Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-048 | 25th April 2012 00:27

Some closure features of locally testable affine-invariant properties


Authors: Alan Guo, Madhu Sudan
Publication: 25th April 2012 00:30
Downloads: 2788


We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less natural property that has been studied before. Previously such results were known for "single-orbit characterized" affine-invariant properties, which known to be a subclass of locally testable ones, and are potentially a strict subclass. The fact that the intersection of locally-testable affine-invariant properties are locally testable could have been derived from previously known general results on closure of property testing under set-theoretic operations, but was not explicitly observed before. The closure under sum and lifts is implied by an affirmative answer to a central question attempting to characterize locally testable affine-invariant properties, but the status of that question remains wide open.

Affine-invariant properties are clean abstractions of commonly studied, and extensively used, algebraic properties such linearity and low-degree. Thus far it is not known what makes affine-invariant properties locally testable --- no characterizations are known, and till this work it was not clear if they satisfied any closure properties. This work shows that the class of locally testable affine-invariant properties are closed under some very natural operations. Our techniques use ones previously developed for the study of "single-orbit characterized" properties, but manage to apply them to the potentially more general class of all locally testable ones via a simple connection that may be of broad interest in the study of affine-invariant properties.

ISSN 1433-8092 | Imprint