Testing Low-Degree Polynomials over Prime Fields

We present an efficient randomized algorithm to test if a given function f: F script sign _p ⁿ F script sign _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 ^2t/p-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 ^t+1/p-1) points.