Testing low-degree polynomials over prime fields

Abstract

We present an efficient randomized algorithm to test if a given function f: Fnp → Fp (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 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/2 Our result is almost optimal since any such algorithm must query f on at least points. © 2009 Wiley Periodicals, Inc.