Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-079 | 9th May 2011 20:40

On Sums of Locally Testable Affine Invariant Properties



Affine-invariant properties are an abstract class of properties that generalize some
central algebraic ones, such as linearity and low-degree-ness, that have been
studied extensively in the context of property testing. Affine invariant properties
consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all
properties that form an $\mathbb{F}_q$-vector space and are invariant under affine
transformations of the domain. Almost all the known locally testable affine-invariant
properties have so-called ``single-orbit characterizations'' --- namely they are
specified by a single local constraint on the property, and the ``orbit'' of this
constraint, i.e., translations of this constraint induced by affine-invariance.
Single-orbit characterizations by a local constraint are also known to imply local
testability. Despite this prominent role in local testing for affine-invariant
properties, single-orbit characterizations are not well-understood.

In this work we show that properties with single-orbit characterizations are closed under
``summation''. Such a closure does not follow easily from definitions, and our proof uses
some of the rich developing theory of affine-invariant properties. To complement this
result, we also show that the property of being an $n$-variate low-degree polynomial over
$\mathbb{F}_q$ has a single-orbit characterization (even when the domain is viewed as $\mathbb{F}_{q^n}$
and so has very few affine transformations). This allows us to exploit known results on
the single-orbit characterizability of ``sparse'' affine-invariant properties to show the
following: The sum of any sparse affine-invariant property (properties satisfied by
$q^{O(n)}$-functions) with the set of degree $d$ multivariate polynomials over $\mathbb{F}_q$ has
a single-orbit characterization (and is hence locally testable) when $q$ is prime.

Our result leads to the broadest known family of locally testable
affine-invariant properties and gives rise to some intriguing
questions/conjectures attempting to classify all locally testable
affine-invariant properties.

ISSN 1433-8092 | Imprint