DocumentCode :
2075156
Title :
Testing low-degree polynomials over prime fields
Author :
Jutla, Charanjit S. ; Patthak, Anindya C. ; Rudra, Atri ; Zuckerman, David
Author_Institution :
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
fYear :
2004
fDate :
17-19 Oct. 2004
Firstpage :
423
Lastpage :
432
Abstract :
We present an efficient randomized algorithm to test if a given function f : Fp n → Fp (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 1/ε + t·p2rp-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 Ω(1/ε + pr+1p-1/) points.
Keywords :
Reed-Muller codes; polynomials; randomised algorithms; generalized Reed-Muller codes; low-degree polynomial testing; prime fields; randomized algorithm; Automatic testing; Codes; Computer science; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-2228-9
Type :
conf
DOI :
10.1109/FOCS.2004.64
Filename :
1366262
Link To Document :
بازگشت