\input zb-basic
\input zb-ioport
\iteman{io-port 05940170}
\itemau{Ben-Sasson, Eli; Grigorescu, Elena; Maatouk, Ghid; Shpilka, Amir; Sudan, Madhu}
\itemti{On sums of locally testable affine invariant properties.}
\itemso{Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17--19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 400-411 (2011).}
\itemab
Summary: 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. In this work we show that properties with single-orbit characterizations are closed under ``summation''. 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). As a consequence we find that 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. We conclude with some intriguing questions/conjectures attempting to classify all locally testable affine-invariant properties.
\itemrv{~}
\itemcc{}
\itemut{property testing; symmetries; direct sums; error-correcting codes}
\itemli{doi:10.1007/978-3-642-22935-0\_34}
\end