Some closure features of locally testable affine-invariant properties

[摘要] 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 well-studied property, which creates some interesting affine-invariant properties over large domains, from properties over smaller domains. Previously such results were known for ;;single-orbit characterized;; affine-invariant properties, which are 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.

[发布机构] Massachusetts Institute of Technology