  Let $\cal{P}$ be an affine invariant property of functions $\mathbb{F}_p^n
\to [R]$ for fixed $p$ and $R$. We show that if $\cal{P}$ is locally testable
with a constant number of queries, then one can estimate the distance of a
function $f$ from $\cal{P}$ with a constant number of queries. This was
previously unknown even for simple properties such as cubic polynomials over
$\mathbb{F}_2$.
  Our test is simple: take a restriction of $f$ to a constant dimensional
affine subspace, and measure its distance from $\cal{P}$. We show that by
choosing the dimension large enough, this approximates with high probability
the global distance of $f$ from $\cP$. The analysis combines the approach of
Fischer and Newman [SIAM J. Comp 2007] who established a similar result for
graph properties, with recently developed tools in higher order Fourier
analysis, in particular those developed in Bhattacharyya et al. [STOC 2013].

Computational Complexity