Premium
Testing low‐degree polynomials over prime fields
Author(s) -
Jutla Charanjit S.,
Patthak Anindya C.,
Rudra Atri,
Zuckerman David
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20262
Subject(s) - degree (music) , prime (order theory) , mathematics , polynomial , combinatorics , integer (computer science) , discrete mathematics , function (biology) , finite field , computer science , physics , mathematical analysis , acoustics , evolutionary biology , biology , programming language
We present an efficient randomized algorithm to test if a given function f : p n→ 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 O ( $ O({{1}\over{\epsilon}}+t.p^{{2t \over p-1}+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 ε from every degree t polynomial, then our algorithm rejects f with probability at least $ {1\over 2} $ . Our result is almost optimal since any such algorithm must query f on at least $ \Omega ( {1 \over \epsilon} + p^ {t+1 \over p-1})$ points. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009