Testing Low-Degree Polynomials over Prime Fields.

Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman

Abstract

We present an efficient randomized algorithm to test if a given function f : F/sub p/ /sup n/ /spl rarr/ F/sub 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 /spl epsiv/ > 0, the algorithm queries f at 1//spl epsiv/ + t/spl middot/p/sup 2r/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 /spl Omega/(1//spl epsiv/ + p/sup r+1/p-1/) points.
BibTeX
@article{jutla2009testing,
  author = {Charanjit S. Jutla and Anindya C. Patthak and Atri Rudra and David Zuckerman},
  title = {{Testing Low-Degree Polynomials over Prime Fields.}},
  journal = {Random Struct. Algorithms},
  year = {2009},
  doi = {10.1002/rsa.20262},
}

Loading related content...

Figure