Abstract
We present an efficient randomized algorithm to test if a given function f : F_p^n \to F_p (where p is a prime) is a low-degree polynomial. This gives a local test for Generalized Reed-Muller codes over prime fields. For a given integer t and a given real ε > 0, the algorithm queries f at \frac{1}{\varepsilon } + t \cdot p^{\frac{{2t}}{{p - 1}} + 0(1)} points to determine whether f can be described by a polynomial of degree at most t. If f is indeed a polynomial of degree at most t, our algorithm always accepts, and if f has a relative distance at least \varepsilon from every degree t polynomial, then our algorithm rejects f with probability at least \frac{1}{2}. Our result is almost optimal since any such algorithm must query f on at least \Omega (\frac{1}{\varepsilon } + p^{\frac{{t + 1}}{{p - 1}}} ) points.