Testing Low-Degree Polynomials over Prime Fields

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.

Authors

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

Keywords

• Polynomials
• Computer science
• Automatic testing
• Codes
• Low-degree Polynomials
• Prime Field
• Polynomial Of Degree
• Degree Of Variability
• Random Points
• Field Size
• Linear Constraints
• Testing Algorithm
• Codeword
• Exact Characteristics
• Dual Coding
• Polynomials In Variables