Charanjit S. Jutla,
Anindya C. Patthak, Atri Rudra
and David Zuckerman
Testing Low-Degree Polynomials Over Prime Fields
Abstract :
Much recent research in computational complexity
has been due to the concept of Probabilistically Checkable
Proofs (PCPs).
Perhaps the most striking application of PCPs has been in proving limitations
for approximating certain NP-hard problems.
Interestingly, most of these PCPs
use error-correcting codes.
In particular they require the following property of the code:
given a received word,
one has to determine (with high probability)
whether it is indeed a codeword or far from being one
while looking at very few positions of the received word.
Codes with local testers that can
efficiently compute the above approximate answers are called
locally testable codes
(LTCs).
Amazingly, such testers exist that can perform this task by looking
at only a constant number of positions.
One of the most important codes in this context are
Reed-Muller codes. These codes are generalizations of Reed-Solomon
codes, which have played an important roles in the recent progress in list
decoding. Local
testers for Reed-Muller codes formed an integral part of the proof of the
famous PCP theorem. However, almost all previous results dealt with
Reed-Muller codes for the case when the degree parameter was smaller
than
the size of the alphabet on which the code is defined. However, Reed-Muller
codes that have more practical applications operate in the opposite
regime-- the degree parameter is greater than the size of the alphabet.
In this work we designed efficient local testers for Reed-Muller codes
that operate in the regime of practical interest mentioned above. The number
of queries that our testers make is almost optimal.
Versions