Theory of Computing
-------------------
Title : A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes
Authors : Noga Ron-Zewi and Madhu Sudan
Volume : 9
Number : 25
Pages : 783-807
URL : http://www.theoryofcomputing.org/articles/v009a025
Abstract
--------
Over a finite field $F_q$, the $(n,d,q)$-Reed-Muller code is the code
given by evaluations of $n$-variate polynomials of total degree at
most $d$ on all points (of $F_q^n$). The task of testing if a
function $f:F_q^n \to F_q$ is close to a codeword of an $(n,d,q)$-
Reed-Muller code has been of central interest in complexity theory
and property testing. The query complexity of this task is the minimal
number of queries that a tester can make (minimum over all testers of
the maximum number of queries over all random choices) while accepting
all Reed-Muller codewords and rejecting words that are $\delta$-far
from the code with probability $\Omega(\delta)$. (In this work we
allow the constant in the $\Omega$ to depend on $d$.)
For codes over a prime field $F_q$ the optimal query complexity is
well-known and known to be $\Theta(q^{\lceil (d+1)/(q-1)\rceil})$, and
the test consists of testing if $f$ is a degree-$d$ polynomial on a
randomly chosen $(\lceil (d+1)/(q-1) \rceil)$-dimensional affine
subspace of $F_q^n$. If $q$ is not a prime, then the above quantity
remains a lower bound, whereas the previously known upper bound grows
to $O(q^{\lceil (d+1)/(q - q/p) \rceil})$ where $p$ is the
characteristic of the field $F_q$. In this work we give a new upper
bound of $(c q)^{(d+1)/q}$ on the query complexity, where $c$ is a
universal constant. Thus for every $p$ and sufficiently large $q$ this
bound improves over the previously known bound by a polynomial factor.
In the process we also give new upper bounds on the "spanning weight"
of the dual of the Reed-Muller code (which is also a Reed-Muller
code). The spanning weight of a code is the smallest integer $w$ such
that codewords of Hamming weight at most $w$ span the code. The main
technical contribution of this work is the design of tests that test a
function by _not_ querying its value on an entire subspace of the
space, but rather on a carefully chosen (algebraically nice) subset of
the points from low-dimensional subspaces.
An earlier version of this paper appeared in the
Proceedings of the 16th International Workshop
on Randomization and Computation (RANDOM'12),
pages 639-650, 2012.