Testing low-degree polynomials over prime fields

We present an efficient randomized algorithm to test if a given function f : F_p ⁿ → 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 1/ε + t·p^2rp-1+O(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 e from every degree t polynomial, then our algorithm rejects f with probability at least 1/2. Our result is almost optimal since any such algorithm must query f on at least Ω(1/ε + p^r+1p-1/) points.