Testing low‐degree polynomials over prime fields

We present an efficient randomized algorithm to test if a given function f :   p n→ 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 O ( $ O({{1}\over{\epsilon}}+t.p^{{2t \over p-1}+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 ε from every degree t polynomial, then our algorithm rejects f with probability at least $ {1\over 2} $ . Our result is almost optimal since any such algorithm must query f on at least $ \Omega ( {1 \over \epsilon} + p^ {t+1 \over p-1})$ points. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009