Sparse Affine-Invariant Linear Codes Are Locally Testable
Eli Ben‐Sasson, Noga Ron‐Zewi, Madhu Sudan · 2012
We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field Fqand an extension field Fqn, a property is a set of functions mapping Fqnto Fq. The property is said to be affine-invariant if it is invariant under affine transformations of Fqn, and it is said to be sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. [RANDOM 2009] and followed by Kaufman and Lovett [FOCS 2011]. The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.