  Affine-invariant codes are codes whose coordinates form a vector space over a
finite field and which are invariant under affine transformations of the
coordinate space. They form a natural, well-studied class of codes; they
include popular codes such as Reed-Muller and Reed-Solomon. A particularly
appealing feature of affine-invariant codes is that they seem well-suited to
admit local correctors and testers.
  In this work, we give lower bounds on the length of locally correctable and
locally testable affine-invariant codes with constant query complexity. We show
that if a code $\mathcal{C} \subset \Sigma^{\mathbb{K}^n}$ is an $r$-query
locally correctable code (LCC), where $\mathbb{K}$ is a finite field and
$\Sigma$ is a finite alphabet, then the number of codewords in $\mathcal{C}$ is
at most $\exp(O_{\mathbb{K}, r, |\Sigma|}(n^{r-1}))$. Also, we show that if
$\mathcal{C} \subset \Sigma^{\mathbb{K}^n}$ is an $r$-query locally testable
code (LTC), then the number of codewords in $\mathcal{C}$ is at most
$\exp(O_{\mathbb{K}, r, |\Sigma|}(n^{r-2}))$. The dependence on $n$ in these
bounds is tight for constant-query LCCs/LTCs, since Guo, Kopparty and Sudan
(ITCS `13) construct affine-invariant codes via lifting that have the same
asymptotic tradeoffs. Note that our result holds for non-linear codes, whereas
previously, Ben-Sasson and Sudan (RANDOM `11) assumed linearity to derive
similar results.
  Our analysis uses higher-order Fourier analysis. In particular, we show that
the codewords corresponding to an affine-invariant LCC/LTC must be far from
each other with respect to Gowers norm of an appropriate order. This then
allows us to bound the number of codewords, using known decomposition theorems
which approximate any bounded function in terms of a finite number of
low-degree non-classical polynomials, upto a small error in the Gowers norm.

Computational Complexity