ECCC-Report TR11-079https://eccc.weizmann.ac.il/report/2011/079Comments and Revisions published for TR11-079en-usMon, 09 May 2011 20:41:46 +0300
Paper TR11-079
| On Sums of Locally Testable Affine Invariant Properties |
Eli Ben-Sasson,
Elena Grigorescu,
Ghid Maatouk,
Amir Shpilka,
Madhu Sudan
https://eccc.weizmann.ac.il/report/2011/079Affine-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.Mon, 09 May 2011 20:41:46 +0300https://eccc.weizmann.ac.il/report/2011/079