Authors Noga Ron-Zewi, Madhu Sudan,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2012
A New Upper Bound on the
Query Complexity of Testing
Generalized Reed-Muller Codes∗
Noga Ron-Zewi† Madhu Sudan
Received October 5, 2012; Revised June 11, 2013; Published October 2, 2013
Abstract: Over a finite field Fq , 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 Fnq ). The task
of testing if a function f : Fnq → Fq 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 δ -far from the code with probability Ω(δ ). (In this
work we allow the constant in the Ω to depend on d.)
For codes over a prime field Fq the optimal query complexity is well-known and known
to be Θ(qd(d+1)/(q−1)e ), and the test consists of testing if f is a degree-d polynomial on a
randomly chosen (d(d + 1)/(q − 1)e)-dimensional affine subspace of Fnq . If q is not a prime,
∗ 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.
† Research was conducted while the author was an intern at Microsoft Research New-England, Cambridge, MA, and
supported by the Israel Ministry of Science and Technology.
ACM Classification: H.1.1, F.1.3
AMS Classification: 68W20, 68Q87
Key words and phrases: Locally testable codes, affine-invariant codes, Reed-Muller codes, query
complexity
© 2013 Noga Ron-Zewi and Madhu Sudan
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a025
N OGA RON -Z EWI AND M ADHU S UDAN
then the above quantity remains a lower bound, whereas the previously known upper bound
grows to O(qd(d+1)/(q−q/p)e ) where p is the characteristic of the field Fq . In this work we give
a new upper bound of (cq)(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.
1 Introduction
In this work we present new upper bounds on the query complexity of testing Reed-Muller codes, the
codes obtained by evaluations of multivariate low-degree polynomials, over general fields. In the process
we also give new upper bounds on the spanning weight of Reed-Muller codes. We explain these terms
and our results below.
We start with the definition of Reed-Muller codes. Let Fq denote the finite field on q elements.
Throughout we will let q = ps for prime p and integer s. The Reed-Muller codes have two parameters
in addition to the order of the field, namely the degree d and number n of variables. The (n, d, q)-Reed-
Muller code RM[n, d, q] is the set of functions from Fnq to Fq that are evaluations of n-variate polynomials
of total degree at most d.
1.1 Testing Reed-Muller codes
We define the notion of testing the “Reed-Muller” property as a special case of property testing. We let
{Fnq → Fq } denote the set of all functions mapping Fnq to Fq . A property F is simply a subset of such
functions. For f , g : Fnq → Fq we say the distance between them δ ( f , g) is the fraction of points of Fnq
where they disagree. We let δ ( f , F) denote the minimum distance between f and a function in F. We say
f is δ -close to F if δ ( f , F) ≤ δ and δ -far otherwise.
A (k, ε)-tester for the property F ⊆ {Fnq → Fq } is a randomized algorithm that makes at most k
queries to an oracle for a function f : Fnq → Fq and accepts if f ∈ F and rejects f 6∈ F with probability at
least ε · δ ( f , F).
For fixed d and q, we consider the query complexity of testing the property of being a degree-d
multivariate polynomial over Fq . Specifically, the query complexity k = k(d, q), is the minimum integer
such that there exists an ε > 0 such that for all n there is a (k, ε)-tester for the RM[n, d, q] property. (So
the “soundness” parameter ε of the tester is allowed to depend on q and d, but not on n.)
The query complexity of low-degree testing is a well-studied question and has played a role in many
results in computational complexity including in the PCP theorem ([2] and subsequent works), and in the
works of Viola and Wigderson [18] and Barak et al. [3]. Many of these results depend not only on a tight
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 784
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
analysis of k(d, q) but also a tight analysis of the parameter ε, but in this work we only focus on the first
quantity. Below we describe what was known about these quantities.
For the case when d is (sufficiently) smaller than the order of the field, the works of Rubinfeld and
Sudan [17] and Friedl and Sudan [9] show that k(d, q) = d + 2 (provided d < q − q/p). For the case
when q = 2 and d is arbitrary, this quantity was analyzed in the work of Alon et al. [1] who show that
k(d, 2) = 2d+1 (exactly). Jutla et al. [12] and Kaufman and Ron [13] explored this question for general q
and d (the former only considered prime q) and showed that k(d, q) ≤ qd(d+1)/(q−q/p)e . In [13] it is also
shown that the bound is tight (to within a factor of q) if q is a prime. However for the non-prime case the
only known lower bound on the query complexity was k(d, q) ≥ q(d+1)/(q−1) (which is roughly the upper
bound raised to the power of (p − 1)/p). In the following sections we describe the conceptual reason for
this gap in knowledge.
In this work we give a new upper bound on k(d, q) which is closer to the lower bound when p is a
constant and d and q are going to infinity. We state our main theorem below.
Theorem 1.1 (Main). Let q = ps for prime p and positive integer s. Then there exists a constant cq ≤ 3q4
such that for every d and n, the Reed-Muller code RM[n, d, q] has a (k, ε)-tester, for
(d+1)/(q(p−1)) (d+1)/q
k = k(d, q) ≤ cq · 2 p−1 + p − 1 q .
and ε = min {1/2, 1/((2k + 1)(k − 1))}. In particular k(d, q) ≤ 3q4 · (3q)(d+1)/q .
We note that the constant cq is not optimized in our proofs and it seems quite plausible that it can be
improved using more careful analysis. The more serious factor (especially when one considers a constant
q and d → ∞) is the constant factor multiplying q in the base of the exponent. Our techniques do seem
to be unable to improve this beyond (2 p−1 + p − 1)1/(p−1) which is always between 2 and 3 (while the
lower bounds suggest a constant which is close to 1). We note however that when p goes to infinity the
bound on k(d, q) tends to cq · (2q)(d+1)/q .
We note that the above result does not compare well with previous bounds if one take the “soundness”
parameter (ε) into account. Previous results by Bhattacharyya et al. [7] for q = 2 and Haramaty et
al. [11] for general q give a (k0 , ε0 )-tester for ε0 depending only on q (but independent of d) and
k0 = qd(d+1)/(q−q/p)e . To get such a soundness independent of d, Theorem 1.1 yields a (k3 , ε1 )-tester for
ε1 being some universal constant. Thus for small q and growing d this is worse than the results of [7, 11].
However for d and q growing at the same rate (for instance) our result does give the best bounds even if
we want the soundness to be some absolute constant.
Theorem 1.1 is proved by proving that the Reed-Muller code RM[n, d, q] has a “k-single-orbit
characterization” (a notion we will define later, see Definition 2.2 and Theorem 2.4). This will imply the
testing result immediately by a result of Kaufman and Sudan [15].
1.2 Spanning weight
It is well-known (cf. [5]) that the query complexity of testing a linear code C is lower bounded by the
“minimum distance” of its dual, where the minimum distance of a code is the minimum weight of a
non-zero codeword. (The weight of a word is simply the number of non-zero coordinates.) Applied to
the Reed-Muller code RM[n, d, q] this suggests a lower bound on the query complexity via the minimum
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 785
N OGA RON -Z EWI AND M ADHU S UDAN
distance of its dual, which also turns out to be a Reed-Muller code. Specifically the dual of RM[n, d, q] is
RM[n, n(q − 1) − d − 1, q]. The minimum distance of the latter is well-known and is (roughly) q(d+1)/(q−1)
and this leads to the tight analysis of the query complexity of Reed-Muller codes over prime fields.
Over non-prime fields however this bound has not been matched, so one could turn to potentially
stronger lower bounds. A natural such bound would be the “spanning weight” of the dual code, namely
the minimum weight w such that codewords of the dual of weight at most w span the dual code. It is easy
to show that to achieve any positive ε (even going to 0 as n → ∞) a (k, ε)-tester must make at least w
queries (on some random choices), where w is the spanning weight of the dual. However, since we were
not able to find such a proof in existing literature, we include a proof of this latter fact in Section 2.3.
Somewhat surprisingly, the spanning weight of the Reed-Muller code does not seem well-understood.
(Some partial understanding comes from [8].) Since for a linear code, the spanning weight of its dual
code is a lower bound on the query complexity of the code, our result gives new upper bounds on this
spanning weight. Specifically, we have
Corollary 1.2. Let q = ps for prime p and positive integer s. Then there exists a constant cq ≤ 3q4 such
that for every d and n, the Reed-Muller code RM[n, n(q − 1) − d − 1, q] has a spanning weight of at most
(d+1)/(q(p−1)) (d+1)/q
cq · 2 p−1 + p − 1 ·q ≤ 3q4 · (3q)(d+1)/q .
1.3 Qualitative description and techniques
Our tester differs from previous ones in some qualitative ways. All previously analyzed testers for
low-degree testing roughly worked as follows: They picked a large enough dimension t (depending on
q and d, but not n) and verified that the function to be tested was a degree-d polynomial on a random
t-dimensional affine subspace. The final aspect was verified by querying the function on the entire
t-dimensional space, thus leading to a query complexity of qt . The minimal choice of the dimension t
that allows this test to detect functions that are not degree-d polynomials with positive probability is
termed the “testing dimension” (see, for instance, [11]), and this quantity is well-understood, and equals
tq,d = d(d + 1)/(q − q/p)e.
Any improvement to the query complexity of the test above requires two features: (1) For some
choices of the tester’s randomness, the set of queried points should span a tq,d -dimensional space. (2) For
all choices of the tester’s randomness, it should make o(qtq,d ) queries. Finding such a useful subset of Fnq
turns out to be a non-trivial task. The fortunate occurrence that provides the basis for our tester is that
such sets of points can indeed be found, and even (in retrospect) systematically.
To illustrate the central idea, consider the setting of n = 2, d = q − 1 and q = 2s for some large s.
While the naive test would query the given function f : F2q → Fq at all q2 points, we wish to query only
O(q) points. Our test, for this simple setting is the following: We pick a random affine-transformation
T : F2q → F2q and test that the function f ◦ T has a zero “inner-product” with the function g : F2q → Fq
given by g(x, y) = (1/y)((x + y)q−1 − xq−1 ). Here “inner-product” is simply the quantity ∑α,β ∈Fq ( f ◦
T )(α, β )g(α, β ). It can be verified that the function g is zero very often and indeed takes on non-zero
values on at most 3q = O(q) points in F2q . So querying f (α, β ) at these O(q) points suffices. The more
interesting question is: Why is this test complete and sound?
Completeness is also easy to verify. It can be verified, by some simple manipulations that any
monomial of the form xi y j with i + j < q has a zero inner-product with g and by linearity of the test it
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 786
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
follows that all polynomials of total degree at most d have a zero inner product with g. Since the degree of
functions is preserved under affine-transformations, it then follows that f ◦ T also has zero inner-product
with g for every polynomial f of total degree at most d.
Finally, we turn to the soundness. Here we appeal to the emerging body of work on affine-invariant
linear properties (linear properties that are preserved under affine-transformations), which allows us to
focus on very specific monomials and to verify that their inner-product with g is non-zero. In particular,
we use a “monomial extraction” lemma (from [15]) which allows us to focus on the behavior of our
tests only on monomials, as opposed to general polynomials. Further the theory also allows us to focus
on specific monomials due to a “monomial spread” lemma (also from [15]) which we use to prove that
every affine-invariant family which contains some monomials of degree greater than d also contains some
canonical monomials of degree slightly larger than d. In the special case of polynomials of degree at most
q − 1, these lemmas allow us to focus on only bivariate monomials of degree q, namely the monomials
xi yq−i for 1 ≤ i ≤ q − 1 and for these monomials one can again verify that their inner-product with g is
non-zero. Using the general methods in the theory of affine-invariant property testing, one can conclude
that all polynomials of degree greater than d are rejected with positive probability.
Extending the above result to the general case turns out relatively clean, again using methods from the
study of testing of affine-invariant linear properties. The extension to general n is immediate. Extending
to other degrees involves some intuitive ways of combining tests, with analysis that get simplified by the
emerging theory. These combinations yield the query complexity of roughly (3q)(d+1)/q . We however
attempt to reduce the constant in front of q in the base of this expression and manage to get an expression
that tends to 2 when p goes to infinity. In order to do so we abstract the function g as being the derivative
of the function xq−1 in direction y, and extend it to use iterative derivatives. This yields the best tests we
give in the paper.
Organization In Section 2 we introduce some of the standard background material from the study of
affine-invariant linear properties and use the theory to provide restatements of our problem. In Section 3
we introduce the main novelty of our work, which provides a restricted version of our test while achieving
significant savings over standard tests. In Section 4 we build on the test from the previous section and
extend it to get a tester for the general case.
2 Background and restatement of problem
We start by introducing some of the background material that leads to some reformulations of the
main theorem we wish to prove. We first introduce the notions of “constraints” and “(single-orbit)
characterizations,” which leads to a first reformulation of our main theorem (see Theorem 2.4). We
then give some sufficient conditions to recognize such characterizations, and this leads to a second
reformulation of our main theorem (see Theorem 2.14).
2.1 Single-orbit characterizations
In this section we use the fact that Reed-Muller codes form a “linear, affine-invariant property.” We recall
these notions first. Given a finite field Fq a property is a set of functions F mapping Fnq to Fq . The property
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 787
N OGA RON -Z EWI AND M ADHU S UDAN
is said to be linear if it is an Fq -vector space, i. e., ∀ f , g ∈ F and α ∈ Fq we have α f + g ∈ F. The property
is said to be affine-invariant if it is invariant under affine-transformations of the domain, i. e., ∀ f ∈ F it is
the case that f ◦ T is also in F for every affine-transformation T : Fnq → Fnq given by T (x) = A · x + β for
A ∈ Fn×n n 1
q , β ∈ Fq . It can be easily verified that RM[n, d, q] is linear and affine-invariant for every n, d, q.
The main tool used so far for constructing testers for affine-invariant linear properties is a structural
theorem which shows that every linear affine-invariant property that is k-single-orbit characterizable is
also k-locally testable. In order to describe the notion of single-orbit characterization we start with a
couple of definitions.
r
Definition 2.1 (k-constraint, k-characterization). A k-constraint C = α, λ i i=1 on {Fnq → Fq } is given
by a vector α = (α1 , . . . , αk ) ∈ (Fnq )k together with r vectors λ i = (λi,1 , . . . , λi,k ) ∈ Fkq for 1 ≤ i ≤ r. We
say that the constraint C accepts a function f : Fnq → Fq if ∑kj=1 λi, j f (α j ) = 0 for all 1 ≤ i ≤ r. Otherwise
we say that Crejects f .
Let F ⊆ Fnq → Fq be a linear property. A k-characterization of F is a collection of k-constraints
C1 , . . . ,Cm on {Fnq → Fq } such that f ∈ F if and only if C j accepts f , for every j ∈ {1, . . . , m}.
It is well-known [5] that every k-locally testable linear property must have a k-characterization. In the
case of affine-invariant linear families some special characterizations are known to lead to k-testability.
We describe these special characterizations next.
r
Definition 2.2 (k-single-orbit characterization). Let C = α, λ i i=1 be a k-constraint on {Fnq → Fq }.
The orbit of C under the set of affine-transformations is the set of k-constraints
r n n
{T ◦C}T = T (α1 ), . . . , T (αk ) , λ i i=1 T : Fq → Fq is an affine-transformation .
We say that C is a k-single-orbit characterization of F if the orbit of C forms a k-characterization of F.
The following theorem, due to Kaufman and Sudan [15], says that k-single-orbit characterization
implies local testability.
Theorem 2.3 (Single-orbit characterization implies local testability, [14, Theorem 2.9]). Let F ⊆
Fq → Fq be an affine-invariant linear family. If F has a k-single-orbit characterization, then F has a
n
(k, ε)-tester for ε = min {1/2, 1/((2k + 1)(k − 1))}.
In view of the above theorem, it suffices to find a single-orbit characterization of RM[n, d, q] to test it.
The following theorem, which we prove in the rest of this paper, thus immediately implies Theorem 1.1.
Theorem 2.4. Let q = ps for prime p, and let n, d be arbitrary positive integers. Then the Reed-Muller
code RM[n, d, q] has a k-single-orbit characterization for
(d+1)/(q(p−1))
k ≤ cq · 2 p−1 + p − 1 · q(d+1)/q ,
where cq ≤ 3q4 .
1 We note that as in [15] we do not require A to be non-singular. Thus the affine-transformations we consider are not
necessarily permutations from Fnq to Fnq .
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 788
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
2.2 Constraints vs. monomials
One of the main simplifications derived from the study of affine-invariant linear properties is that it
suffices to analyze the performance of constraints on “monomials” as opposed to general polynomials.
This allows us to rephrase our target (a single-orbit characterization of RM[n, d, q]) in somewhat simpler
terms. Below we describe some of the essential notions, namely the “degree set,” the “border set” and
the relationship of these to single-orbit characterizations. This leads to a further reformulation of our
main theorem as Theorem 2.14. Variations of most of the results and notions presented in this section
appeared in previous works [15, 10, 6, 4]. In all the above works, with the exception of [15], the notions
were specialized to the case of univariate functions mapping Fqn to Fq that are invariant over the set of
affine-transformations over Fqn . In this work we focus on these notions in the context of affine-invariant
linear properties over the domain Fnq .
Let F ⊆ {Fnq → Fq } be a linear affine-invariant family of functions. Note that every member of
{Fnq → Fq } can be written uniquely as a polynomial in Fq [x1 , x2 , . . . , xn ] of degree at most q − 1 in
each variable. For a monomial ∏ni=1 xidi over n variables, we define its degree to be the vector d =
(d1 , d2 , . . . , dn ) and we define its total degree to be ∑ni=1 di . For a function f : Fnq → Fq we denote its
support, denoted supp( f ), to be the set of degrees in the support of the associated polynomial. I. e.,
supp( f ) = {d ∈ {0, . . . , q − 1}n | cd 6= 0} where f (x) = ∑d cd xd . The degree set Deg(F) of F is simply
the union of the supports of the functions in F, i. e., Deg(F) = ∪ f ∈F supp( f ).
While the degree set of the Reed-Muller codes are natural to study, they are also natural in more
general contexts. The following lemma from [15] says that every affine-invariant linear property from Fnq
to Fq is uniquely determined by its degree set.
Lemma 2.5 (Monomial extraction lemma, [14, Lemma 4.2]). Let F ⊆ Fnq → Fq be an affine-invariant
linear property. Then F has a monomial basis, that is, F is the set of all polynomials supported on
monomials of the form xd where d ∈ Deg(F).2
One main structural feature of the degree sets of affine-invariant linear properties is that they are
p-shadow-closed. Before giving the definition of a shadow-closed set of degrees we need to introduce
a bit of notation. For a pair of integers a, b let a = ∑ j a j p j , b = ∑ j b j p j be their base-p representation,
respectively. We say that b is in the p-shadow of a, and denote this b ≤ p a, if b j ≤ a j for all j. For a pair
of integer vectors d = (d1 , d2 , . . . , dn ), e = (e1 , e2 , . . . , en ) we say that e ≤ p d if ei ≤ p di for every i.
Definition 2.6 (Shadow-closed set of degrees). For a vector of integers d = (d1 , d2 , . . . , dn ) of length
n, the p-shadow of d is the set Shadow p (d) = {e = (e1 , e2 , . . . , en ) | e ≤ p d}. For a subset S of integer
S
vectors of length n we let Shadow p (S) = d∈S Shadow p (d). Finally, we say that S is p-Shadow-closed if
Shadow p (S) = S.
The following lemma from [14] says that the degree set of every affine-invariant linear property over
Fnq is p-shadow-closed.
2 Our language is somewhat different from that of [14]. After translation, their lemma says that all monomials xd are
contained in F. The other direction saying F is contained in the span of such monomials is immediate from the definition of
Deg(F).
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 789
N OGA RON -Z EWI AND M ADHU S UDAN
Lemma 2.7 (Monomial spread lemma, [14, Lemma 4.6]). Let F ⊆ Fnq → Fq be an affine-invariant
linear property. Then Deg(F) is p-shadow-closed.
Remark 2.8. Note that Lemma 4.6 in [14] actually shows that Deg(F) is closed under an even stronger
notion of p-shadow in which a pair of integer vectors d = (d1 , d2 , . . . , dn ), e = (e1 , e2 , . . . , en ) is said
to satisfy e ≤ p d if ∑ni=1 ei, j ≤ ∑ni=1 di, j for all j, where ei = ∑ j ei, j p j , di = ∑ j di, j p j are the base-p
representations of the integers di , ei respectively. It can be verified that if d, e satisfy e ≤ p d according to
our definition then they also satisfy e ≤ p d according to the definition of [14]. The converse, however, is
false.
A central element used in the proof of the above lemma and other aspects in the study of affine-
invariant linear properties is Lucas’s theorem, which we also need.
Theorem 2.9 (Lucas’s Theorem). The binomial coefficient ni is non-zero mod p if and only if i ≤ p n.
The fact that the degree set of a linear affine-invariant family is p-shadow-closed motivates the notion
of a “border” set, the set of minimal elements (under ≤ p ) that are not in Deg(F).
Definition 2.10 (Border). For an affine-invariant linear family F ⊆ Fnq → Fq , its border set, denoted
Border(F), is the set
/ Deg(F) but ∀e0 ≤ p e, e0 6= e, e0 ∈ Deg(F)} .
Border(F) = {e ∈ {0, . . . , q − 1}n | e ∈
The relationship between the degree set and the border set of an affine-invariant linear family and
single-orbit characterization is given by the following lemma. This lemma says that for an affine-invariant
linear family, in order to establish k-single-orbit characterization it suffices to exhibit a k-constraint whose
orbit accepts all monomials of the form xd for d ∈ Deg(F) and rejects all monomials of the form xb for
b ∈ Border(F). It is similar in spirit to Lemma 3.2 of [4] which shows that a similar result holds for
affine-invariant linear properties over Fqn .
Lemma 2.11. Let F ⊆ {Fnq → Fq } be an affine-invariant linear property and let C be a constraint. Then
C is a single-orbit characterization of F if the orbit of C accepts every monomial xd for d ∈ Deg(F) and
rejects every monomial xb for b ∈ Border(F).
Proof. We need to show that for every affine-transformation T : Fnq → Fnq the constraint T ◦C accepts all
functions f ∈ F, while for every f ∈ / F there exists an affine-transformation T such that T ◦C rejects f .
Since the set of monomials x for d ∈ Deg(F) forms a basis for F, clearly we have that C accepts all
d
functions f ∈ F. The fact that F is affine-invariant implies in turn that for every affine-transformation T
the constraint T ◦C also accepts all functions f ∈ F.
It remains to show that for every f ∈ / F there exists an affine-transformation T : Fnq → Fnq such that
T ◦C rejects f . Suppose in contrary that there exists a function f ∈ / F such that the orbit of C accepts f ,
and let
e = { f 0 : Fn → Fq | T ◦C accepts f 0 for every affine-transformation T } .
F q
Note that F
e is a linear affine-invariant property, and that our assumption on f implies that f ∈ F.
e
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 790
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
Since f ∈/ F, and since Deg(F) forms a basis for F, there exists a monomial xe in the support of f such
/ Deg(F). The Monomial Extraction Lemma (Lemma 2.5) then implies that xe is also contained
that e ∈
in F.
e Let b be a minimal degree (with respect to ≤ p ) such that b ≤ p e and b ∈ / Deg(F). Then from the
definition of the border we have that b ∈ Border(F). Furthermore, since F e is linear and affine-invariant
and e ∈ Deg(F),e the monomial spread lemma (Lemma 2.7) implies that b ∈ Deg(F) e and in particular
xb ∈ F.
e But this implies in turn that xb is accepted by the orbit of C, a contradiction to our assumption
that all degrees in the border of F are rejected by the orbit of C.
In order to describe the border of the Reed-Muller family we shall use the following definition.
Definition 2.12. For an integer d, let d0 , d1 , . . . be its base-p expansion, i. e., the d j satisfy 0 ≤ d j < p
and d = ∑∞j=0 d j p j . Let bi (d) = pi + ∑∞j=i d j p j .
Note that bi (d) > d for every i and conversely, for every integer e > d there exists an index i such
that bi (d) ≤ p e. The bi (d) are useful in describing the border monomials of the Reed-Muller family, as
formalized below.
Proposition 2.13. For every n, d, q, where q = ps for a prime p, we have
( )
n
Deg RM[n, d, q] = d = (d1 , . . . , dn ) ∈ {0, . . . , q − 1}n ∑ d j ≤ d
and
j=1
( )
n
n
Border RM[n, d, q] ⊆ e = (e1 , . . . , en ) ∈ {0, . . . , q − 1} ∑ e j = bi (d) for some 0 ≤ i ≤ s .
j=1
Proof. The fact that the degree set contains all d with ∑nj=1 d j ≤ d is immediate from the definitions.
Now consider f such that ∑nj=1 f j > d. To verify the correctness of the border, we wish to show that there
exists e ≤ p f and 0 ≤ i ≤ s such that ∑nj=1 e j = bi (d). Let ` be the least index such that ∑`j=1 f j = f > d.
Note that f ≤ d + q − 1, since f` ≤ q − 1. Now let f (0) , f (1) , . . . denote the base-p expansion of f and let
d (0) , d (1) , . . . denote the base-p expansion of d. Since f > d, there must exist a largest index i such that
f (i) > d (i) and for all j > i, f ( j) = d ( j) . For this choice of i, note that bi (d) ≤ p f and one can reduce each
f j to the corresponding e j so that e ≤ p f and ∑nj=1 e j = bi (d).
It remains to be shown that i ≤ s. For this part note that if bi (d) > bi−1 (d) then bi (d) ≥ bi−1 (d) + pi−1 .
Thus for all i > s, we have either bi (d) = bs (d) or bi (d) ≥ bs (d) + ps > d + q. But since f ≤ d + q − 1 it
follows that we never need to use i > s.
Combining Lemma 2.11 and Proposition 2.13 we have that Theorem 2.4 follows immediately from
Theorem 2.14 below.
Theorem 2.14. Let q = ps for a prime p. Then there exists a k-constraint C on Fnq → Fq whose orbit
accepts all monomials of total degree at most d and rejects all monomials of total degree bi (d) for
0 ≤ i ≤ s, for
(d+1)/(q(p−1)) (d+1)/q
k ≤ 3q4 · 2 p−1 + p − 1 ·q .
The rest of this paper will be devoted to proving Theorem 2.14.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 791
N OGA RON -Z EWI AND M ADHU S UDAN
2.3 Spanning weight of the dual code is a lower bound on query complexity
In this section we prove that for a linear code, the spanning weight of its dual code is a lower bound on
the query complexity of a tester for the code.
Lemma 2.15. Let C ⊆ Fnq → Fq be a linear code that has a (k, ε)-tester for some integer k and ε > 0.
Then the spanning weight of its dual code C⊥ is at most k.
For the proof of the above lemma we shall use a result due to Ben-Sasson et al. [5], saying that when
considering testers for linear codes C ⊆ Fnq → Fq it is enough to consider testers of simple form, named
canonical testers. Such testers are specified by a distribution on dual codewords, and on a given word w,
they pick a codeword u of the dual according to this distribution and accept the word w if and only if
hw, ui = 0. The formal definition follows.
Definition 2.16 (Canonical tester). A (k, ε)-canonical tester for a linear code C ⊆ Fnq → Fq is a (k, ε)-
tester for C which is specified by a distribution ρ on elements u ∈ C⊥ of hamming weight at most k. In
order to test a given word w ∈ Fnq , the tester picks a random element u ∈ C⊥ according to the distribution
ρ and accepts w if and only if hu, wi = 0.
The following proposition from [5] says that, up to some loss in the soundness, tests may always
assumed to be canonical.
Proposition 2.17 (Theorem 3.3,[5]). For every ε > 0 there exists ε 0 > 0 such that the following holds.
Suppose that a linear code C ⊆ Fnq → Fq has a (k, ε)-tester. Then C has a (k, ε 0 )-canonical tester.
Proof of Lemma 2.15. From Proposition 2.17 we may assume that C has a (k, ε)-canonical tester T
defined by a distribution ρ on codewords of C⊥ of hamming weight at most k. Let U ⊆ C⊥ be the set of
words in the support of the distribution ρ. We claim that U must contain a basis for C⊥ . Since all words
in the support of the distribution ρ are codewords of C⊥ of hamming weight at most k, this will imply in
turn that there exists a basis for C⊥ which consists of elements of hamming weight at most k and hence
the spanning weight of C⊥ is at most k.
Suppose in contradiction that U does not contain a basis for C⊥ , so |span (U) | < |C⊥ |. This implies
in turn that |(span (U))⊥ | > |C| and hence there exists w ∈ / C such that hu, wi = 0 for every u ∈ U.
Consequently, T will accept w with probability one—a contradiction.
3 Canonical monomials and a new constraint
In this section we introduce the notion of “canonical monomials” of a given degree—simple monomials
that appear in every affine-invariant linear property containing monomials of a given degree. We then give
a constraint that rejects canonical monomials of some special degrees, while accepting all monomials of
lower degrees.
Later, in Section 4, we show how to use this to build a constraint whose orbit accepts all monomials
of total degree at most d while rejecting all monomials of total degree bi (d), which suffices to get
Theorem 2.14.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 792
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
Definition 3.1 (Canonical monomials). Let q = ps for a prime p. The canonical monomial of (total)
degree d over Fq is the monomial ∏`i=1 xidi which satisfies ∑`i=1 di = d, di = q − q/p for all 2 ≤ i ≤ `,
0 ≤ d1 ≤ q − 1 and d1 + q − q/p > q − 1.
We note that [11] used a different canonical monomial (cf. Definition 4.1., [11]) for the proof of
their improved bounds on testing Reed-Muller codes. Our different choice of canonical monomial is
needed to construct single-orbit characterizations which improve on those given in [11] in terms of the
number of queries. The main property of the canonical monomial that we will use in Section 4.3 to prove
Theorem 2.14 is that every affine-invariant linear family that contains any monomial of total degree d
also contains the canonical monomial of degree d. (See Lemma 4.8.) This will imply in turn that if we
can find constraints that reject this canonical monomial their orbit will reject every monomial of total
degree d.
3.1 A new constraint on monomials of total degree < p(q − q/p)
The main technical novelty in our paper is a k-constraint C that accepts all monomials of total degree
strictly less than p(q − q/p) in p variables but rejects the canonical monomial of degree p(q − q/p) (note
that the latter monomial also has p variables) for k = (2 p−1 + p − 1)q p−1 . We state the lemma below and
devote the rest of this section to proving this lemma.
Lemma
3.2 (Main technical lemma). For every q which is a power of a prime p there exists a k-constraint
C on Fnq → Fq which accepts all monomials of total degree smaller than p(q − q/p) in p variables and
p q−q/p
rejects the canonical monomial ∏i=1 xi of degree p(q − q/p) over Fq , where k = (2 p−1 + p − 1)q p−1 .
It will be convenient for us to represent the constraint C as a p-variate polynomial over Fq . More
precisely, suppose that g(x) is a p-variate polynomial g(x) ∈ Fq [x1 , x2 , . . . , x p ] that is non-zero on at
most k points in Fqp . We associate with g(x) the k-constraint C = (α, λ ), α = (α1 , . . . , αk ) ∈ (Fqp )k ,
λ = (λ1 , . . . , λk ) ∈ Fkq , where the vector α consists of all points in Fqp on which g(x) is non-zero and
λ j = g(α j ) for all 1 ≤ j ≤ k. Clearly, for every function f : Fqp → Fq it holds that
k
∑ λ j f (α j ) = ∑ g(β1 , . . . , β p ) · f (β1 , . . . , β p ) .
j=1 β1 ,...,β p ∈Fq
Thus for our purposes it suffices to find a p-variate polynomial g(x) ∈ Fq [x1 , x2 , . . . , x p ] with at most
k non-zero points in Fqp such that
∑ g(β1 , . . . , β p ) · M(β1 , . . . , β p ) = 0
β1 ,...,β p ∈Fq
for every monomial in p variables of total degree smaller than p(q − q/p) and
∑ g(β1 , . . . , β p ) · M(β1 , . . . , β p ) 6= 0
β1 ,...,β p ∈Fq
when M(x) is the canonical monomial of degree p(q − q/p).
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 793
N OGA RON -Z EWI AND M ADHU S UDAN
We start by describing a polynomial P(x) that will satisfy the conditions we expect in g above. The
best way to describe this polynomial is via the notion of directional derivatives. Let f : Fq → Fq be a
function. Define the derivative of f in direction y ∈ Fq as fy (x) = f (x + y) − f (x). Define the iterated
derivatives as
|I|+1
fy1 ,...,y` (x) = ( fy1 ,...,y`−1 )y` (x) = ∑ (−1) f x + ∑ yi .
I⊆[`] i∈I
Let f (x) be the polynomial f (x) = xq−1
p . Our polynomial P(x) will be defined as follows.
fx1 ,...,x p−1 (x p ) ∑I⊆[p−1] (−1)|I|+1 (x p + ∑i∈I xi )q−1
P(x) = = . (3.1)
x1 · · · x p−1 x1 · · · x p−1
To see that P(x) is indeed a polynomial we need to show that fx1 ,...,x p−1 (x p ) is divisible by x1 · · · x p−1 .
This follows from the following lemma.
Lemma 3.3. Let f be a univariate polynomial over Fq . Then the polynomial fy1 ,...,y` (x), as a polynomial
in variables x, y1 , . . . , y` , is divisible by y1 , . . . , y` .
Proof. The proof is by induction on `. For ` = 1, if we write f (x) = ∑d cd xd then we have
fy1 (x) = f (x + y1 ) − f (x) = ∑ cd (x + y1 )d − ∑ cd xd
d d
d d
d d−i i d d−i i
= ∑ cd ∑ x y1 − ∑ cd x d = ∑ cd ∑ x y1 .
d i=0 i d d>0 i=1 i
Thus all monomials in fy1 (x) contain the variable y1 and hence fy1 (x) is divisible by y1 .
Next assume that g(x) := fy1 ,...,y`−1 (x) is divisible by y1 , . . . , y`−1 . We shall show that fy1 ,...,y` (x) is
divisible by y1 , . . . , y` . Let g(x) = ∑d c0d xd .
fy1 ,...,y` (x) = g(x + y` ) − g(x) = ∑ c0d (x + y` )d − ∑ c0d xd
d d
d
d
0 d d−i i 0 d 0 d d−i i
= ∑ cd ∑ x y` − ∑ cd x = ∑ cd ∑ x y` .
d i=0 i d d>0 i=1 i
So all monomials in fy1 ,...,y` (x) contain the variable y` and hence fy1 ,...,y` (x) is divisible by y` . Furthermore,
by the induction hypothesis we have that g(x) is divisible by y1 , . . . , y`−1 , so all monomials in both
g(x + y` ) and g(x) are divisible by y1 , . . . , y`−1 . Consequently, all monomials in fy1 ,...,y` (x) are divisible
by y1 , . . . , y`−1 , so fy1 ,...,y` (x) is divisible by y1 , . . . , y`−1 .
In order to prove our main technical Lemma 3.2 it suffices to show that the number of non-zero points
of P(x) in Fqp is at most (2 p−1 + p − 1)q p−1 , that it accepts all monomials in p variables of total degree
smaller than p(q − q/p), and that it rejects the canonical monomial of degree p(q − q/p). We prove
these three claims in Lemmas 3.4, 3.6 and 3.8 below, respectively. Given these three lemmas our main
technical Lemma 3.2 is immediate. We start with bounding the number of non-zeros of P(x).
Lemma 3.4. The number of non-zero points of P(x) in Fqp is at most (2 p−1 + p − 1)q p−1 .
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 794
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
Proof. Let β = (β1 , . . . , β p ) ∈ Fqp . Suppose first that all first p − 1 coordinates of β are non-zero, so that
the denominator of P(β ) is non-zero. Suppose furthermore that all terms of the form (β p + ∑i∈I βi )q−1 in
the numerator of P(β ) are non-zero. Then in this case we have that
p−1 p−1
∑I⊆[p−1] (−1)|I|+1 · 1 ∑i=0 i (−1)i
P(β ) = =− = 0.
β1 · · · β p−1 β1 · · · β p−1
Thus we have that whenever β1 , . . . , β p−1 are all non-zero, P(β ) can be non-zero only if at least one
of the terms of the form (β p + ∑i∈I βi )q−1 in its numerator equals zero. Note that each such term has
exactly q p−1 assignments in Fqp that make it zero. Since the number of terms in the numerator is 2 p−1 ,
the total number of points in Fqp that satisfy that at least one of the terms in the numerator equals zero is
at most 2 p−1 · q p−1 .
Concluding, we have that there are at most 2 p−1 q p−1 vectors β ∈ Fqp which satisfy that β1 , β2 , . . . , β p−1
are all non-zero and in addition P(β ) 6= 0. Since there are at most (p − 1)q p−1 elements β ∈ Fqp in which
at least one of the first p − 1 coordinates is zero, we conclude that the number of elements β ∈ Fqp such
that P(β ) 6= 0 is at most
2 p−1 q p−1 + (p − 1)q p−1 = (2 p−1 + p − 1)q p−1 .
We shall show later (in Lemma 3.9) that the bound on the number of non-zero points of P(x) obtained
in Lemma 3.4 is essentially tight. Next we show that the constraint C associated with P(x) accepts
all monomials in p variables of total degree smaller than p(q − q/p). For this we need the following
well-known fact.
Claim 3.5. Let q be a prime-power, and let i be an integer from {0, 1, . . . , q − 1}. Then
(
−1 i = q−1,
∑ βi = 0 otherwise.
β ∈Fq
Proof. Recall that the multiplicative group of F∗q is cyclic and let γ be a generator of this group. Then for
all i ∈ {1, . . . , q − 2} we have
q−1
(γ i )q−1 − 1 1−1
∑ β = ∑ (γ i ) j = γ i ·
i
γi − 1
= γi · i
γ −1
= 0,
β ∈Fq j=1
whereas for i = q − 1 we have that
∑ β q−1 = ∑ 1 = q − 1 = −1 ,
β ∈Fq β ∈F∗q
and for i = 0 we have
∑ β0 = ∑ 1 = q = 0.
β ∈Fq β ∈Fq
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 795
N OGA RON -Z EWI AND M ADHU S UDAN
Lemma 3.6. Let C be the constraint associated with P(x). Then C accepts all monomials in p variables
of total degree smaller than p(q − q/p).
Proof. Let m be a monomial in p variables of total degree d < p(q − q/p). We shall show that
∑ m(β1 , β2 , . . . , β p ) · m0 (β1 , β2 , . . . , β p ) = 0
β1 ,...,β p ∈Fq
for every monomial m0 in P(x). This will show in turn that
∑ m(β1 , . . . , β p ) · P(β1 , . . . , β p ) = 0
β1 ,...,β p ∈Fq
and hence C accepts m.
Let m0 be a monomial in P(x). First note that all monomials in the numerator of P(x) have total
degree exactly q − 1 and hence all monomials in P(x) have total degree q − 1 − (p − 1) = q − p. Thus m0
has total degree q − p, and m · m0 is a monomial of total degree at most
q − p + d < q − p + p(q − q/p) = p(q − 1)
(after reducing individual degrees of variables mod q if necessary). Since m · m0 is a monomial in p
variables, by pigeonhole principle there exists a variable xi in m · m0 of degree smaller than q − 1. Without
0 p
loss of generality suppose that x1 has degree d 0 < q − 1 in m · m0 , and let m · m0 = x1d · ∏i=2 xidi .
Thus we have
p p
0 d0 di d0 di
∑ (m · m )(β1 , . . . , β p ) = ∑ β1 · ∏ βi = ∑ β1 ∏ ∑ βi = 0 ,
β1 ,...,β p ∈Fq β1 ,...,β p ∈Fq i=2 β1 ∈Fq i=2 βi ∈Fq
where the last equality follows from Claim 3.5 above and the fact that d 0 < q − 1.
We complete the proof of Lemma 3.2 by showing that the constraint C associated with P(x) rejects the
canonical monomial of degree p(q − q/p). In order to prove this, we shall use Kummer’s Theorem which
generalizes Lucas’s Theorem (Theorem 2.9) and gives a condition for when a multinomial coefficient
n n!
= 6≡ 0 mod p
γ1 , γ2 , . . . , γk γ1 !γ2 ! · · · γk !
(it can be proved via repeated applications of Lucas’s Theorem).
Theorem 3.7 (Kummer’s Theorem, [16]). Let n, γ1 , γ2 , . . . , γk be integers such that n = γ1 + γ2 + · · · + γk .
Then the multinomial coefficient
n n!
= 6≡ 0 mod p
γ1 , γ2 , . . . , γk γ1 !γ2 ! · · · γk !
if and only if γ1 , γ2 , . . . , γk sum to n in base-p without carry.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 796
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
Lemma 3.8. Let C be the constraint associated with P(x). Then C rejects the canonical monomial of
degree p(q − q/p) over Fq .
p q−q/p
Proof. The canonical monomial of degree p(q − q/p) over Fq is the monomial m = ∏i=1 xi . Let
0 p q/p−1
m = ∏i=1 xi . We claim that
∑ (m · m0 )(β1 , . . . , β p ) 6= 0 , (3.2)
β1 ,...,β p ∈Fq
while for every other monomial m00 6= m0 in the support of P(x) it holds that
∑ (m · m00 )(β1 , . . . , β p ) = 0 . (3.3)
β1 ,...,β p ∈Fq
Thus in order to prove the lemma it will suffice to show that the monomial m0 is in the support of P(x).
We start by showing (3.2).
p p
0 q−1 q−1
∑ (m · m )(β1 , . . . , β p ) = ∑ ∏ βi = ∏ ∑ βi = (−1) p ,
β1 ,...,β p ∈Fq β1 ,...,β p ∈Fq i=1 i=1 βi ∈Fq
where the last equality follows from Claim 3.5 above.
Next we show that (3.3) holds for every monomial m00 6= m0 in the support of P(x). Let m00 6= m0 be a
monomial in the support of P(x). Then m00 is a monomial of total degree q − p and the fact that m00 6= m0
implies that m00 has a variable of degree smaller than (q − p)/p = q/p − 1. Without loss of generality
suppose that the variable x1 has degree smaller than q/p − 1 in m00 and note that this implies that the
0 p
variable x1 has degree d 0 < q − 1 in m · m00 . Let m · m00 = x1d · ∏i=2 xidi . Then we have
p p
00 d0 di d0 q−1
∑ (m · m )(β1 , . . . , β p ) = ∑ β1 ∏ βi = ∑ β1 ∏ ∑ βi = 0,
β1 ,...,β p ∈Fq β1 ,...,β p ∈Fq i=2 β1 ∈Fq i=2 βi ∈Fq
d0
where the last equality holds since ∑β1 ∈Fq β1 = 0 due to Claim 3.5 above and the fact that d 0 < q − 1.
It remains to show that the monomial m0 is in the support of P(x). This happens in turn if and only if
the monomial
p
q/p−1 q/p
e = x1
m ∏ xi
i=2
is in the numerator of P(x). Note that of all terms of the form (x p + ∑i∈I xi )q−1 in the numerator of P(x),
the monomial m e can only belong to the support of
q−1
x p + ∑ xi = (x1 + x2 + · · · + x p )q−1 .
i∈[p−1]
Thus it suffices to show that the monomial m e belongs to the support of (x1 + x2 + · · · + x p )q−1 .
In order to show the above we resort to Kummer’s Theorem. Expanding (x1 + x2 + · · · + x p )q−1
q−1
we have that the coefficient of the monomial m e is γ1 ,...,γ p for γ1 = q/p − 1 and γi = q/p for all 2 ≤
i ≤ p. Noting that γ1 , . . . , γ p sum to q − 1 without carry in base-p, Kummer’s Theorem implies that
q−1
γ1 ,...,γ p is non-zero mod p. This implies in turn that m e is contained in the support of the polynomial
(x1 + x2 + · · · + x p )q−1 , thus completing the proof of the lemma.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 797
N OGA RON -Z EWI AND M ADHU S UDAN
Given Lemmas 3.4, 3.6 and 3.8 the proof of Lemma 3.2 is immediate.
Proof of Lemma 3.2. Let P(x) be the polynomial given in (3.1), and let C be the constraint on Fqp → Fq
associated with P(x). From Lemma 3.4 we have that the number of non-zero points of P(x) in Fqp is at
most (2 p−1 + p − 1)q p−1 , and hence C is a ((2 p−1 + p − 1)q p−1 )-constraint. Lemma 3.6 implies that C
accepts all monomials of total degree smaller than p(q − q/p), while Lemma 3.8 implies that C rejects
the canonical monomial of degree p(q − q/p).
3.2 Tightness of our analysis
Next we show that the upper bound on the number of non-zero points of P(x) in Fqp given in Lemma 3.4
is essentially tight.
Lemma 3.9. The number of non-zero points of P(x) in Fqp is at least
(2 p−1 − p − 1)q p−1 − 2 p−1 (2 p−1 − 1)q p−2 .
Proof. We will show that the numerator of P(x) is non-zero for at least
2 p−1 q p−1 − 2 p−1 (2 p−1 − 1)q p−2
elements in Fqp . Since the denominator of P(x) is zero for at most (p − 1)q p−1 elements in Fqp this will
show that P(x) is non-zero for at least
2 p−1 q p−1 − 2 p−1 (2 p−1 − 1)q p−2 − (p − 1)q p−1
points in Fqp .
Let β = (β1 , . . . , β p ) be a random point in Fqp . Let E be the event that the numerator of P(β ) is
non-zero. Our goal will be to show that
Pr[E] ≥ 2 p−1 /q − 2 p−1 (2 p−1 − 1)/q2 .
For a subset I ⊆ [p − 1] let EI be the event that (β p + ∑i∈I βi )q−1 = 0. Let E 0 be the event that exactly one
of the events EI holds. Clearly, E 0 ⊆ E and hence it suffices to show that
Pr[E 0 ] ≥ 2 p−1 /q − 2 p−1 (2 p−1 − 1)/q2 .
Note that Pr[EI ] = 1/q for all I ⊆ [p − 1] and Pr[EI ∩ EJ ] = 1/q2 for all I 6= J, I, J ⊆ [p − 1] since
β p + ∑i∈I βi = 0 and β p + ∑ j∈J β j = 0 are linearly independent linear equations.
Thus we have that
Pr[E 0 ] ≥ ∑ Pr[EI ] − ∑ Pr[E I ∩ EJ ]
I⊆[p−1] J⊆[p−1],J6=I
2
= ∑ 1/q − ∑ 1/q
I⊆[p−1] J⊆[p−1],J6=I
= 2 p−1 (1/q − (2 p−1 − 1)/q2 )
= 2 p−1 /q − 2 p−1 (2 p−1 − 1)/q2 .
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 798
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
4 Proof of Theorem 2.14
In this section we use Lemma 3.2 to prove Theorem 2.14. This part is done in several steps. In Section 4.1
we extend the constraint from the previous section to obtain constraints rejecting canonical monomials of
degree d + 1, while accepting all monomials of total degree at most d for an arbitrary integer d. Next,
in Section 4.2 we combine the various constraints from the previous step to find one constraint which
rejects all the canonical monomials of degree bi (d) for every 0 ≤ i ≤ s, while accepting all monomials of
total degree at most d, for an arbitrary integer d. Finally, in Section 4.3, we prove Theorem 2.14. In this
part, we use some of the standard facts about affine-invariance to conclude that the orbit of the constraint
from the previous step must reject all monomials (and not just the canonical monomials) of total degree
bi (d) for 0 ≤ i ≤ s while accepting all monomials of total degree at most d.
4.1 Rejecting canonical monomials of arbitrary degree d + 1
We start by showing how the constraint guaranteed by Lemma 3.2 can be turned, via an operation on
constraints that we call the product operation, into a constraint which rejects the canonical monomial of
degree d + 1 and accepts all monomials of total degree at most d for an arbitrary integer d. This step is
given in the following lemma.
Lemma 4.1. For every q which is a power of a prime p, and for every pair d, n of integers there exists
a k-constraint C on {Fnq → Fq } which accepts all monomials of total degree at most d and rejects the
canonical monomial of degree d + 1 over Fq , where
(d+1)/(q(p−1)) (d+1)/q
k ≤ q2 · 2 p−1 + p − 1 ·q .
For the proof of the above lemma first introduce the product operation. For a pair of vectors
γ = (γ1 , . . . , γn1 ) and γ 0 = (γ10 , . . . , γn0 2 ) let γ ◦ γ 0 = (γ1 , . . . , γn1 , γ10 , . . . , γn0 2 ) denote their concatenation.
Definition 4.2 (Product of constraints). Let
n (1) or1
(1)
C1 = α , λ i
i=1
be a k1 -constraint on Fnq1 → Fq , and let
n (2) or2
(2)
C2 = α , λ i
i=1
be a k2 -constraint on Fnq2 → Fq . Their product C = C1 ⊗C2 is the (k1 · k2 )-constraint
n or1 ,r2
C = α, λ (i1 ,i2 )
i1 =1,i2 =1
on Fnq1 +n2 → Fq , where α ∈ (Fnq1 +n2 )k1 ×k2 and λ (i1 ,i2 ) ∈ (Fq )k1 ×k2 for all 1 ≤ i1 ≤ r1 , 1 ≤ i2 ≤ r2 , and
are defined as follows:
(1) (2) (1) (2)
α( j1 , j2 ) = α j1 ◦ α j2 , λ(i1 ,i2 ),( j1 , j2 ) = λi1 , j1 · λi2 , j2
for all 1 ≤ j1 ≤ k1 , 1 ≤ j2 ≤ k2 , 1 ≤ i1 ≤ r1 , 1 ≤ i2 ≤ r2 .
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 799
N OGA RON -Z EWI AND M ADHU S UDAN
Proposition 4.3. Let C1 be a k1 -constraint on Fnq1 → Fq which accepts all monomials xd with d ∈ D1
and rejects all monomials xb with b ∈ B1 , and let C2 be a k2 -constraint on Fnq2 → Fq which accepts
all monomials xd with d ∈ D2 and rejects all monomials xb with b ∈ B2 . Then C1 ⊗ C2 is a (k1 · k2 )-
constraint on Fnq1 +n2 → Fq which accepts all monomials xd 1 ◦e2 and xe1 ◦d 2 where d 1 ∈ D1 , d 2 ∈ D2 and
e1 ∈ {0, . . . , q − 1}n1 , e2 ∈ {0, . . . , q − 1}n2 are arbitrary, and rejects all monomials of the form xb1 ◦b2
where b1 ∈ B1 and b2 ∈ B2 .
Proof. Let f = f 1 ◦ f 2 where f 1 ∈ {0, . . . , q − 1}n1 , f 2 ∈ {0, . . . , q − 1}n2 . Then for every 1 ≤ i1 ≤ r1 ,
1 ≤ i2 ≤ r2 we have that
k1 k2 k1 k2
(1) (2) (1) (2) f
∑ ∑ λ(i1 ,i2 ),( j1 , j2 ) (α( j1 , j2 ) ) f = ∑ ∑ λi1 , j1 · λi2 , j2 · α j1 ◦ α j2
j1 =1 j2 =1 j1 =1 j2 =1
k1 k2
(1) (2) (1) f 1 (2) f 2
= ∑ ∑ λi1 , j1 · λi2 , j2 · α j1 α j2
j1 =1 j2 =1
k1 k2
(1) (1) f (2) (2) f 2
= ∑ λi1 , j1 α j1 1 · ∑ λi2 , j2 α j2 .
j1 =1 j2 =1
Hence C accepts all monomials of the form xd 1 ◦e2 and xe1 ◦d 2 where d 1 ∈ D1 , d 2 ∈ D2 and e1 ∈
{0, . . . , q − 1}n1 , e2 ∈ {0, . . . , q − 1}n2 are arbitrary and rejects all monomials of the form xb1 ◦b2 where
b1 ∈ B1 , b2 ∈ B2 .
The product operation, applied to the constraint given by Lemma 3.2, suffices for proving Lemma 4.1
when p(q − q/p) divides d + 1. However, since this is not always the case we need to consider also
testing univariate monomials of degree at most q − 2. The following lemma covers this case.
Lemma 4.4 (Testing univariate monomials of degree at most q − 2, (cf. [17])). Let d be an integer from
{0, 1, . . . , q − 2}. Then there exists a (d + 2)-constraint C on {Fq → Fq } which accepts all monomials xe
for e ≤ d and rejects the monomial xd+1 .
Proof. Let C = (α, λ ) be the (d + 2)-constraint defined as follows. Let α1 , . . . , αd+2 ∈ Fq be distinct
elements (note that they do exist since d + 2 ≤ q). Let λ = (λ1 , . . . , λd+2 ) ∈ Fd+2
q be a non-zero vector
satisfying
d+2
∑ λi αi` = 0 for all ` ∈ {0, . . . , d} .
i=1
Note that such a vector λ exists since each of the constraints above is a homogenous linear constraint on
λ and there are only d + 1 such constraints and d + 2 variables. We claim that
d+2
∑ λi αid+1 6= 0 ,
i=1
since if it were then λ would be in the null space of the Vandermonde matrix [αij ]d+2,d+1
i=1, j=0 . Thus C rejects
x d+1 e
while accepting x for every e ≤ d.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 800
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
Given Proposition 4.3 and Lemma 4.4 we are ready to prove Lemma 4.1.
Proof of Lemma 4.1. Write d + 1 as d + 1 = r + `(q − q/p) where 0 ≤ r ≤ q − 1 and r + q − q/p >
q − 1. Write ` = `0 p + r0 where 0 ≤ r0 < p. Let C1 be the (r + 1)-constraint guaranteed by Lemma 4.4
for the degree r − 1, and let C2 be the (q − q/p + 1)-constraint guaranteed by the same lemma for
the degree q − q/p − 1. Let C3 be the k0 -constraint guaranteed by Lemma 3.2. Finally, let C be the
0 0
((r + 1) · (q − q/p + 1)r · (k0 )` )-constraint which is the product of C1 with r0 copies of C2 and `0 copies
0 0
of C3 . That is, C = C1 ⊗C2⊗r ⊗C3⊗` . We claim that C accepts all monomials of total degree at most d
0
and rejects the canonical monomial of degree d + 1 (If C = α, λ i i ) is a constraint on {Fnq → Fq } for
n0 < n then we extend C to be a constraint on {Fnq → Fq } by concatenating sufficient number of 1’s to
each element α j in the vector α.)
To see this suppose first that m = x1d1 · · · xndn is a monomial of total degree at most d. In this case we
have that either d1 < r or di < q − q/p for some 2 ≤ i ≤ r0 + 1 or
r0 +1+pi
∑ d j < p(q − q/p)
j=r0 +2+p(i−1)
for some 1 ≤ i ≤ `0 . From Proposition 4.3 this implies that the constraint C accepts the monomial m.
Suppose on the other hand that m is the canonical monomial of degree d + 1. Then in this case we
have that all of the variables x2 , . . . , x`+1 are of degree q − q/p and the variable x1 is of degree r. Hence
Proposition 4.3 implies that C rejects the monomial m.
0 0
Finally note that the locality of C is k = (r + 1) · (q − q/p + 1)r · (k0 )` where
d +1
k0 = (2 p−1 + p − 1)q p−1 , `0 ≤ , r ≤ q−1, and r0 ≤ p .
(q − q/p)p
Using the following series of simplifications, we can bound k as claimed.
0 0
k = (r + 1) · (q − q/p + 1)r · ((2 p−1 + p − 1)q p−1 )`
0 0
≤ q · qr · ((2 p−1 + p − 1)q p−1 )`
0 0 0
= q · (2 p−1 + p − 1)` · qr +(p−1)·`
0
≤ q · (2 p−1 + p − 1)` · q((p−1)/p)·`+1
≤ q2 · (2 p−1 + p − 1)(d+1)/((q−q/p)p) · q((p−1)/p)·((d+1)/(q−q/p))
= q2 · (2 p−1 + p − 1)(d+1)/(q(p−1)) · q(d+1)/q .
4.2 Rejecting all canonical monomials in the border simultaneously
Next we show for every integer d the existence of a k-constraint which accepts all monomials of total
degree at most d and rejects all the canonical monomials of degree bi (d) for 0 ≤ i ≤ s simultaneously.
For proving this we shall use the union operation on constraints defined as follows. For an integer k, let
0k denote the all-zeros vector of length k.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 801
N OGA RON -Z EWI AND M ADHU S UDAN
Definition 4.5 (Union of constraints). Let
n (1) or1
(1)
C1 = α , λ i
i=1
be a k1 -constraint on Fnq → Fq and let
n (2) or2
C2 = α (2) , λ i
i=1
be a k2 -constraint on Fnq → Fq . Their union C = C1 ∪C2 is the (k1 + k2 )-constraint
n n 0(2) or2
0(1) r1
o
C = α, λ i ∪ λi
i=1 i=1
on Fnq → Fq defined by
α = α (1) ◦ α (2) ,
0(1) (1)
λi = λ i ◦ 0k2 for all 1 ≤ i ≤ r1 ,
0(2) (2)
λi = 0k1 ◦ λ i for all 1 ≤ i ≤ r2 .
Proposition 4.6. Let C1 be a constraint which accepts all monomials with degrees in D1 and rejects all
monomials with degrees in B1 , and let C2 be a constraint which accepts all monomials with degrees in
D2 and rejects all monomials with degrees in B2 . Then C1 ∪C2 accepts all monomials with degrees in
D1 ∩ D2 and rejects all monomials with degrees in B1 ∪ B2 .
Proof. For every degree e,
k1 +k2 k1
0(1) (1) (1) e
∑ λi, j α ej = ∑ λi, j α j for all 1 ≤ i ≤ r1 ,
j=1 j=1
and similarly
k1 +k2 k2
0(2) (2) (2) e
∑ λi, j α ej = ∑ λi, j α j for all 1 ≤ i ≤ r2 .
j=1 j=1
Thus the constraint C accepts monomials of degree e if and only if both C1 and C2 accept the monomial
of degree e. Hence C accepts all monomials with degrees in D1 ∩ D2 and rejects all monomials with
degrees in B1 ∪ B2 .
Given the above proposition we can now build a constraint which accepts all monomials of total
degree at most d while rejecting all the canonical monomials of degree bi (d) for 0 ≤ i ≤ s.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 802
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
Lemma 4.7. Let q = ps for a prime p and let n, d be arbitrary positive integers. Recall the definition
of the integers bi (d) given in Definition 2.12. Then there exists a k-constraint C on {Fnq → Fq } which
accepts all monomials of total degree at most d and rejects all canonical monomials of degree bi (d) for
0 ≤ i ≤ s, where
(d+1)/(q(p−1)) (d+1)/q
k ≤ 3q4 · 2 p−1 + p − 1 ·q .
Proof. For all 0 ≤ i ≤ s let Ci be the ki -constraint which accepts all monomials of total degree at most
bi (d) − 1 and rejects the canonical monomial of degree bi (d) over Fq as guaranteed by Lemma 4.1 with
ki ≤ q2 · (2 p−1 + p − 1)(d+1+q)/(q(p−1)) · q(d+1+q)/q ≤ 3q3 · (2 p−1 + p − 1)(d+1)/(q(p−1)) · q(d+1)/q .
Ss
Let C = i=0 Ci . Then C is a k-constraint for
s
k = ∑ ki ≤ 3q4 · (2 p−1 + p − 1)(d+1)/(q(p−1)) · q(d+1)/q .
i=0
Proposition 4.6 implies that C accepts all monomials of total degree at most d and rejects all canonical
monomials of degree bi (d) for 0 ≤ i ≤ s, giving the claimed assertion.
4.3 Rejecting all monomials in the border
In order to complete the proof of Theorem 2.14, we show that for the constraint from Lemma 4.7 which
accepts all monomials of total degree at most d while rejecting all the canonical monomials of degree
bi (d), its orbit must accept all monomials of total degree at most d while rejecting all monomials of total
degree bi (d). and thus satisfies the conditions of Theorem 2.14.
We start by stating a simple (but useful) property of canonical monomials.
Lemma 4.8. Let m be a monomial of total degree d, and let F be a linear affine-invariant family
containing m. Then F contains the canonical monomial of degree d over Fq .
For the proof of the above lemma we shall need the following claim.
Claim 4.9. Let q = ps for a prime p, and let m = x1d1 x2d2 be a monomial such that 0 ≤ d1 ≤ q − 1,
0 ≤ d2 ≤ q − 1 and k ≤ p d2 . Let F be an affine-invariant linear family containing m. Then the monomial
m0 = x1d1 +k x2d2 −k is contained in F.
Proof. Let T be the affine-transformation T (x1 , x2 ) = (x1 , x1 + x2 ). Then
d2 d2
d2 i d2 −i d2
m ◦ T = x1d1 (x1 + x2 )d2 = x1d1 ∑ i x1 x2 = ∑ i x1d1 +i x2d2 −i .
i=0 i=0
From Lucas’s Theorem (Theorem 2.9) we have that di2 6≡ 0 mod p if and only if i ≤ p d2 . So all
monomials of the form x1d1 +i x2d2 −i such that i ≤ p d2 are contained in the support of m ◦ T . Since F
is affine-invariant we have that m ◦ T is contained in F and hence the Monomial Extraction Lemma
(Lemma 2.5) implies that m0 is contained in F.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 803
N OGA RON -Z EWI AND M ADHU S UDAN
Next we prove Lemma 4.8 based on Claim 4.9.
Proof of Lemma 4.8. Write d = `(q − q/p) + r0 where r0 < q − q/p. Let m = ∏ni=1 xidi . We start by
d0
showing that F contains a monomial ∏ni=1 xi i which satisfies di0 ≥ q − q/p for every 2 ≤ i ≤ ` + 1.
We shall apply Claim 4.9 iteratively. For a monomial m0 = ∏ni=1 xiei let
`+1
c(m0 ) = ∑ max{0, (q − q/p) − ei } .
i=2
Clearly, c(m0 ) = 0 if and only if ei ≥ q − q/p for all 2 ≤ i ≤ ` + 1. If m satisfies that di ≥ q − q/p for all
2 ≤ i ≤ ` + 1 then we are done, hence assume that there exists 2 ≤ i ≤ ` + 1 such that di < q − q/p. If there
exists a degree j ∈ {1} ∪ {` + 2, . . . , n} such that d j > 0 let pk be such that pk ≤ p d j . Claim 4.9 implies
k k
that m1 := m · xip x−p
j is contained in F. Otherwise, since ∑ni=1 di = d there exists j ∈ {2, . . . , ` + 1} such
that d j > q − q/p. Note that the base-p representation of q − q/p is (q − q/p) = (p − 1) · ps−1 and hence
the fact that d j > q − q/p implies the existence of pk ≤ p d j such that q − q/p + pk ≤ p d j . Claim 4.9
k k
implies that m1 := m · xip x−p j is contained in F in this case as well. Note that in both cases we have that
c(m1 ) < c(m). Also, since di < q − q/p we have that di + pk < q − q/p + q/p < q. Hence all variables in
m1 have degree at most q − 1 (we mention this fact since this will allow us to apply Claim 4.9 iteratively).
If all variables x2 , . . . , x`+1 in m1 have degree at least q − q/p then we are done. Otherwise repeat the
same process as previously to obtain a monomial m2 ∈ F such that the degrees of all variables in m2 are
at most q − 1 and c(m2 ) < c(m1 ). Continuing this way we have that at the i-th step either all variables
x2 , . . . , x`+1 in mi−1 have degree at least q − q/p and hence we are done or that we obtain a monomial
mi ∈ F such that the degrees of all variables in mi are at most q − 1 and c(mi ) < c(mi−1 ). Since the
function c(mi ) strictly declines at each step the process must terminate eventually, and when it terminates
we have that mi satisfies that all variables x2 , . . . , x`+1 in it have degree at least q − q/p.
d0
We have just shown that F contains a monomial m0 = ∏ni=1 xi i where di0 ≥ q − q/p for all 2 ≤ i ≤ ` + 1.
Next we claim that the monomial m e = ∏ni=1 xidi which satisfies de1 = r0 , dei = q − q/p for all 2 ≤ i ≤ ` + 1
e
and dei = 0 for all ` + 2 ≤ i ≤ n is contained in F (note that m e is the canonical monomial of degree d if
and only if r0 + q − q/p > q − 1). To see this note that if m0 = m e then we are done. Otherwise we must
0 0
have that d1 < r . As was the case previously this implies the existence of either ` + 2 ≤ j ≤ n and an
integer k such that pk ≤ p d 0j or 2 ≤ j ≤ ` + 1 such that q − q/p + pk ≤ p d 0j . Claim 4.9 implies that the
k k
monomial m0 · x1p x−pj is contained in F. Note that in the latter monomial the degree of the variable x1
increased, but the degree of all variables x2 , . . . , x`+1 remained at least q − q/p. Continuing this way we
conclude that the monomial m e is contained in F.
0
Finally, note that if r + q − q/p > q − 1 then m e is also the canonical monomial of degree d and hence
we are done. Otherwise we have that q − q/p ≤ p de`+1 and hence Claim 4.9 implies that the monomial
q−q/p −(q−q/p)
e · x1
m · x`+1 is contained in F. The proof is completed by noting that in this case the latter
monomial is the canonical monomial of degree d.
We are now ready for the proof of Theorem 2.14.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 804
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
Proof of Theorem 2.14. From Lemma 4.7 we have a constraint C of arity
(d+1)/(q(p−1)) (d+1)/q
k ≤ 3q4 · 2 p−1 + p − 1 ·q
that accepts every monomial of total degree at most d and rejects every canonical monomial of degree
bi (d) for 0 ≤ i ≤ s.
The constraint C accepts all monomials of total degree at most d and hence C accepts all functions
in RM[n, d, q]. Since RM[n, d, q] is affine-invariant this implies in turn that the orbit of C accepts all
functions in RM[n, d, q] as well, and in particular all monomials of total degree at most d.
It just remains to show that the orbit of C rejects every monomial of total degree bi (d) for 0 ≤ i ≤ s.
Assume for contradiction that the orbit of C accepts a monomial m of total degree bi (d) for some 0 ≤ i ≤ s.
Let F0 be the set of functions accepted by the orbit of C, i. e.,
F0 = { f : Fnq → Fq | T ◦C accepts f for every affine-transformation T } .
We have that F0 is linear and affine-invariant, and contains m, and so by Lemma 4.8 it also contains the
canonical monomial of degree bi (d). So the orbit of C accepts the canonical monomial of degree bi (d)
contradicting the hypothesis about C.
Acknowledgements
We would like to thank Amir Shpilka for suggesting that our tests are related to directional derivatives.
References
[1] N OGA A LON , TALI K AUFMAN , M ICHAEL K RIVELEVICH , S IMON L ITSYN , AND DANA RON:
Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032–4039, 2005. Preliminary
version in RANDOM’03. [doi:10.1109/TIT.2005.856958] 785
[2] S ANJEEV A RORA , C ARSTEN L UND , R AJEEV M OTWANI , M ADHU S UDAN , AND M ARIO
S ZEGEDY: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555,
1998. Preliminary version in FOCS’92. See also at ECCC. [doi:10.1145/278298.278306] 784
[3] B OAZ BARAK , PARIKSHIT G OPALAN , J OHAN H ÅSTAD , R AGHU M EKA , P RASAD R AGHAVEN -
DRA , AND DAVID S TEURER : Making the long code shorter. In Proc. 53rd FOCS, pp. 370–379.
IEEE Comp. Soc. Press, 2012. See also at ECCC. [doi:10.1109/FOCS.2012.83] 784
[4] E LI B EN -S ASSON , E LENA G RIGORESCU , G HID M AATOUK , A MIR S HPILKA , AND M ADHU
S UDAN: On sums of locally testable affine invariant properties. In Proc. 15th Internat. Workshop on
Randomization and Computation (RANDOM’11), pp. 400–411. Springer, 2011. See also at ECCC.
[doi:10.1007/978-3-642-22935-0_34] 789, 790
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 805
N OGA RON -Z EWI AND M ADHU S UDAN
[5] E LI B EN -S ASSON , P RAHLADH H ARSHA , AND S OFYA R ASKHODNIKOVA: Some 3CNF properties
are hard to test. SIAM J. Comput., 35(1):1–21, 2005. Preliminary version in STOC’03. See also at
ECCC. [doi:10.1137/S0097539704445445] 785, 788, 792
[6] E LI B EN -S ASSON AND M ADHU S UDAN: Limits on the rate of locally testable affine-invariant
codes. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’11), pp.
412–423. Springer, 2011. See also at ECCC. [doi:10.1007/978-3-642-22935-0_35] 789
[7] A RNAB B HATTACHARYYA , S WASTIK KOPPARTY, G RANT S CHOENEBECK , M ADHU S UDAN ,
AND DAVID Z UCKERMAN : Optimal testing of Reed-Muller codes. In Proc. 51st FOCS, pp. 488–
497. IEEE Comp. Soc. Press, 2010. See also at ECCC and an overview in “Property Testing”
(Springer 2011). [doi:10.1109/FOCS.2010.54] 785
[8] P ENG D ING AND J ENNIFER D. K EY: Minimum-weight codewords as generators of generalized
Reed-Muller codes. IEEE Trans. Inform. Theory, 46(6):2152–2158, 2000. [doi:10.1109/18.868484]
786
[9] K ATALIN F RIEDL AND M ADHU S UDAN: Some improvements to total degree tests. In Proc. 3rd
Ann. Israel Symp. on Theory of Computing and Systems (ISTCS’95), pp. 190–198. IEEE Comp. Soc.
Press, 1995. See corrected version on the arXiv. [doi:10.1109/ISTCS.1995.377032] 785
[10] E LENA G RIGORESCU , TALI K AUFMAN , AND M ADHU S UDAN: Succinct representation of codes
with applications to testing. SIAM J. Discrete Math., 26(4):1618–1634, 2012. Preliminary version
in RANDOM’09. See also at ECCC. [doi:10.1137/100818364] 789
[11] E LAD H ARAMATY, A MIR S HPILKA , AND M ADHU S UDAN: Optimal testing of multivariate
polynomials over small prime fields. SIAM J. Comput., 42(2):536–562, 2013. Preliminary version
in FOCS’11. See also at ECCC. [doi:10.1137/120879257] 785, 786, 793
[12] C HARANJIT S. J UTLA , A NINDYA C. PATTHAK , ATRI RUDRA , AND DAVID Z UCKERMAN: Testing
low-degree polynomials over prime fields. Random Structures & Algorithms, 35(2):163–193, 2009.
Preliminary version in FOCS’04. [doi:10.1002/rsa.20262] 785
[13] TALI K AUFMAN AND DANA RON: Testing polynomials over general fields. SIAM J. Comput.,
36(3):779–802, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539704445615] 785
[14] TALI K AUFMAN AND M ADHU S UDAN: Algebraic property testing: The role of invariance. Electron.
Colloq. on Comput. Complexity (ECCC), 14(111), 2007. ECCC. 788, 789, 790
[15] TALI K AUFMAN AND M ADHU S UDAN: Algebraic property testing: the role of invariance. In Proc.
40th STOC, pp. 403–412. ACM Press, 2008. See also at ECCC. [doi:10.1145/1374376.1374434]
785, 787, 788, 789
[16] E RNST E DUARD K UMMER: Über die hypergeometrische Reihe. Journal für die reine und ange-
wandte Mathematik, 15:39–83, 1836. EUDML. 796
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 806
O N THE Q UERY C OMPLEXITY OF T ESTING G ENERALIZED R EED -M ULLER C ODES
[17] RONITT RUBINFELD AND M ADHU S UDAN: Robust characterizations of polynomi-
als with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996.
[doi:10.1137/S0097539793255151] 785, 800
[18] E MANUELE V IOLA AND AVI W IGDERSON: Norms, XOR lemmas, and lower bounds for polyno-
mials and protocols. Theory of Computing, 4(7):137–168, 2008. Preliminary version in CCC’07.
[doi:10.4086/toc.2008.v004a007] 784
AUTHORS
Noga Ron-Zewi
Technion - Israel Institute of Technology
nogaz cs techion ac il
https://sites.google.com/site/nogazewi/
Madhu Sudan
Microsoft Research New-England, Cambridge, MA
madhu mit edu
http://people.csail.mit.edu/madhu/
ABOUT THE AUTHORS
N OGA RON -Z EWI is a Ph. D. student at the department of computer science at the Technion-
Israel Institute of Technology, advised by Eli Ben-Sasson and Amir Shpilka. She has a
broad interest in the area of computational complexity, especially in the areas of coding,
communication and pseudo-randomness. A common theme in her works has been the
application of tools and techniques from the mathematical area of additive combinatorics
to open problems in these areas.
M ADHU S UDAN received his Ph. D. from the University of California at Berkeley in 1992.
From 1992 to 1997 he was a research staff member at IBM’s Thomas J. Watson Research
Center. From 1997-2009 he was a faculty member at the Electrical Engineering and
Computer Science Department at the Massachusetts Institute of Technology. He is
currently a Principal Researcher at Microsoft Research New England. His research has
focussed on Probabilistic Checking of Proofs, List-Decoding, Property Testing, and
Semantic Communication.
T HEORY OF C OMPUTING, Volume 9 (25), 2013, pp. 783–807 807