TR11-079 Authors: Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Publication: 9th May 2011 20:41

Downloads: 3074

Keywords:

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.