  The problem of testing low-degree polynomials has received significant
attention over the years due to its importance in theoretical computer science,
and in particular in complexity theory. The problem is specified by three
parameters: field size $q$, degree $d$ and proximity parameter $\delta$, and
the goal is to design a tester making as few as possible queries to a given
function, which is able to distinguish between the case the given function has
degree at most $d$, and the case the given function is $\delta$-far from any
degree $d$ function.
  A tester is called optimal if it makes $O(q^d+1/\delta)$ queries (which are
known to be necessary). For the field of size $q$, the natural $t$-flat tester
was shown to be optimal first by Bhattacharyya et al. for $q=2$, and later by
Haramaty et al. for all prime powers $q$. The dependency on the field size,
however, is a tower-type function.
  We improve the results above, showing that the dependency on the field size
is polynomial. Our approach also applies in the more general setting of lifted
affine invariant codes, and is based on studying the structure of the
collection of erroneous subspaces. i.e. subspaces $A$ such that $f|_{A}$ has
degree greater than $d$. Towards this end, we observe that these sets are
poorly expanding in the affine version of the Grassmann graph and use that to
establish structural results on them via global hypercontractivity. We then use
this structure to perform local correction on $f$.
