  A local tester for an error correcting code $C\subseteq \Sigma^{n}$ is a
tester that makes $Q$ oracle queries to a given word $w\in \Sigma^n$ and
decides to accept or reject the word $w$. An optimal local tester is a local
tester that has the additional properties of completeness and optimal
soundness. By completeness, we mean that the tester must accept with
probability $1$ if $w\in C$. By optimal soundness, we mean that if the tester
accepts with probability at least $1-\epsilon$ (where $\epsilon$ is small),
then it must be the case that $w$ is $O(\epsilon/Q)$-close to some codeword
$c\in C$ in Hamming distance.
  We show that Generalized Reed-Muller codes admit optimal testers with $Q =
(3q)^{\lceil{ \frac{d+1}{q-1}\rceil}+O(1)}$ queries. Here, for a prime power $q
= p^{k}$, the Generalized Reed-Muller code, RM[n,q,d], consists of the
evaluations of all $n$-variate degree $d$ polynomials over $\mathbb{F}_q$.
Previously, no tester achieving this query complexity was known, and the best
known testers due to Haramaty, Shpilka and Sudan(which is optimal) and due to
Ron-Zewi and Sudan(which was not known to be optimal) both required
$q^{\lceil{\frac{d+1}{q-q/p} \rceil}}$ queries. Our tester achieves query
complexity which is polynomially better than by a power of $p/(p-1)$, which is
nearly the best query complexity possible for generalized Reed-Muller codes.
  The tester we analyze is due to Ron-Zewi and Sudan, and we show that their
basic tester is in fact optimal. Our methods are more general and also allow us
to prove that a wide class of testers, which follow the form of the Ron-Zewi
and Sudan tester, are optimal. This result applies to testers for all
affine-invariant codes (which are not necessarily generalized Reed-Muller
codes).
