E. Allen Emerson, Charanjit S. Jutla
SIAM Journal on Computing
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.
E. Allen Emerson, Charanjit S. Jutla
SIAM Journal on Computing
Robert Krauthgamer, Aranyak Mehta, et al.
ICDE 2008
Robert Krauthgamer, James R. Lee, et al.
FOCS 2004
Charanjit S. Jutla, Anindya C. Patthak
IEEE Trans. Inf. Theory