Testing low‐degree polynomials over prime fields
- 10 June 2009
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 35 (2) , 163-193
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
Keywords
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:
- Robust locally testable codes and products of codesRandom Structures & Algorithms, 2006
- Testing Reed–Muller CodesIEEE Transactions on Information Theory, 2005
- Some 3CNF Properties Are Hard to TestSIAM Journal on Computing, 2005
- Improved Low-Degree Testing and its ApplicationsCombinatorica, 2003
- Regular languages are testable with a constant number of queries2003
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Checking computations in polylogarithmic time1991