Testing Low-Degree Polynomials over Prime Fields

Abstract

We present an efficient randomized algorithm to test if a given function f: F script sign pn 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. © 2004 IEEE.