Testing low‐degree polynomials over prime fields

Authors:

Abstract
We present an efficient randomized algorithm to test if a given functionf: 𝔽→ 𝔽p(wherepis a prime) is a low‐degree polynomial. This gives a local test for Generalized Reed‐Muller codes over prime fields. For a given integertand a given real ε > 0, the algorithm queriesfatO($ O({{1}\over{\epsilon}}+t.p^{{2t \over p-1}+1}) $ ) points to determine whetherfcan be described by a polynomial of degree at mostt. Iffis indeed a polynomial of degree at mostt, our algorithm always accepts, and iffhas a relative distance at least ε from every degreetpolynomial, then our algorithm rejectsfwith probability at least$ {1\over 2} $ . Our result is almost optimal since any such algorithm must queryfon at least$ \Omega ( {1 \over \epsilon} + p^ {t+1 \over p-1})$ points. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009
Funding Information
  • NSF (CCR-0310960, CCF-0635339, CCR-9912428, CCR-0310960, CCF-0634811)
  • David and Lucile Packard Fellowship for Science and Engineering

This publication has 20 references indexed in Scilit: