Charles Micchelli
Journal of Approximation Theory
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.
Charles Micchelli
Journal of Approximation Theory
Jaione Tirapu Azpiroz, Alan E. Rosenbluth, et al.
SPIE Photomask Technology + EUV Lithography 2009
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997