Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR11-079 | 9th May 2011 20:40

On Sums of Locally Testable Affine Invariant Properties

TR11-079
Authors: Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan
Publication: 9th May 2011 20:41
Keywords:

Abstract:

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