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 : 𝔽 → 𝔽p (where p is a prime) is a low‐degree polynomial. This gives a local test for Generalized Reed‐Muller codes over pri...
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