On Active and Passive Testing
Noga Alon∗

Rani Hod†

Amit Weinstein‡

arXiv:1307.7364v2 [] 15 Nov 2015

February 27, 2018

Abstract
Given a property of Boolean functions, what is the minimum number of queries required
to determine with high probability if an input function satisﬁes this property or is “far” from
satisfying it? This is a fundamental question in Property Testing, where traditionally the testing
algorithm is allowed to pick its queries among the entire set of inputs. Balcan, Blais, Blum and
Yang have recently suggested to restrict the tester to take its queries from a smaller random
subset of polynomial size of the inputs. This model is called active testing, and in the extreme
case when the size of the set we can query from is exactly the number of queries performed it
is known as passive testing.
We prove that passive or active testing of k-linear functions (that is, sums of k variables
among n over Z2 ) requires Θ(k log n) queries, assuming k is not too large. This extends the case
k = 1, (that is, dictator functions), analyzed by Balcan et. al.
We also consider other classes of functions including low degree polynomials, juntas, and
partially symmetric functions. Our methods combine algebraic, combinatorial, and probabilistic
techniques, including the Talagrand concentration inequality and the Erdős–Rado theorem on
∆-systems.

1

Introduction

Property testing considers the following general problem: given a property P, identify the minimum
number of queries required to determine with high probability whether an input object has the
property P or whether it is “far” from P. This question was ﬁrst formalized by Rubinfeld and
Sudan [24] in the context of Boolean functions.
Deﬁnition 1 ([24]). Let P be a family of Boolean functions and let ǫ > 0. A q-query ǫ-tester for P
is a randomized algorithm that queries an unknown function f : Zn2 → Z2 on q inputs of its choice
and
(i) Accepts with probability at least 2/3 when f ∈ P;
(ii) Rejects with probability at least 2/3 when f is ǫ-far from P, where f is ǫ-far from P if
dist(f, g) := |{x ∈ Zn2 | f (x) 6= g(x)}| ≥ ǫ2n holds for every g ∈ P.
∗

Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978,
Israel and School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540. Email: nogaa@tau.ac.il.
Research supported in part by BSF grant 2012/107, by ISF grant 620/13, by the Israeli I-Core program and by the
Fund for Mathematics.
†
School of Mathematics, Georgia Tech, 686 Cherry st, Atlanta, GA 30332. E-mail: rani.hod@math.gatech.edu.
‡
Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. Email: amitw@tau.ac.il.
Research supported in part by the Israeli I-Core program.

1

We denote the minimal q such that a q-query ǫ-tester for P exists by Qǫ (P).
The main line of research in many works on property testing is to characterize Qǫ (P) for various
properties P. An interesting distinction is identifying properties for which Qǫ (P) is constant (i.e.,
independent of n). For instance, linearity can be tested in a constant number of queries [13]; more
generally, testing if a Boolean function is a polynomial of constant degree can be performed with
a constant number of queries [1, 5, 7, 24]. Testing whether a function depends only on a constant
number of its input variables (that is, if a function is a junta) can also be done with a constant
number of queries [8, 9, 19].
In the deﬁnition above the algorithm can pick its q queries in the entire set Zn2 . Balcan, Blais,
Blum, and Yang [3] suggested to restrict the tester to take its queries from a smaller, typically
random, subset U ⊆ Zn2 . This model is called active testing, in resemblance of active learning (see,
e.g., [16]). Active testing gets more diﬃcult as the size of U decreases, and the extreme case is
when U is a set of q random points (so the algorithm actually has no choice). This is known as
passive testing, or testing from random examples1 , and was studied in [20, 21]. Formally, the next
deﬁnition from [3] extends Deﬁnition 1 to active and passive testers.
Deﬁnition 2. Let P be a family of Boolean functions and let ǫ > 0. A u-sample q-query ǫ-tester
for P is a randomized algorithm that, given a subset U ⊆ Zn2 of size |U | = u, drawn uniformly at
random, queries an unknown function f : Zn2 → Z2 on q inputs from U and
(i) Accepts with probability at least 2/3 when f ∈ P;
(ii) Rejects with probability at least 2/3 when f is ǫ-far from P.
The set U may be chosen with or without repetitions. For our purpose these two options will
be equivalent, as in the parameters considered here the probability of a repetition is negligible.
We denote by Qaǫ (P, u) the minimal q such that a u-sample q-query ǫ-tester for P exists (∞ if
u queries do not suﬃce), and by Qpǫ (P) the minimal q such that a q-sample q-query ǫ-tester (i.e.,
a passive ǫ-tester) for P exists.
We are usually interested in poly (n)-sample testers; for simplicity, we omit the sample size u
from our notation when this is the case.
The following inequality from [3] shows the relation between the query complexity of the diﬀerent
testing models.
Proposition 3 ([3, Theorem A.4.]). For every property P and for every ǫ > 0, Qǫ (P) ≤ Qaǫ (P) ≤
Qpǫ (P).
To provide a simple upper bound on the query complexity of passive testing, we refer to the
more diﬃcult problem of proper passive learning. The most common model of passive learning is
PAC-learning, introduced by Valiant [27].
Deﬁnition 4. Let P be a family of Boolean functions. A q-query ǫ-learning algorithm for P is
a randomized algorithm that, given q random queries from an unknown function f ∈ P, outputs
a Boolean function g : Zn2 → Z2 such that g is ǫ-close to f with probability at least 2/3 (the
underlying probability space is the random queries and the coin tosses of the algorithm). The
algorithm is called proper if it always returns some g ∈ P. We denote the minimal q such that a
proper q-query ǫ-learning algorithm for P exists by Qℓǫ (P).
1
Although the examples could be drawn from a general probability distribution, in this work we focus on the
uniform distribution.

2

The number of queries needed to properly learn a Boolean function essentially bounds from
above the number of queries needed to test it; given the output of a proper learning algorithm, it
remains to verify that the input function is indeed close to it. More formally, we have the following
proposition.
Proposition 5 ([20, Proposition 3.1.1]). For every property P and for every ǫ > 0, Qpǫ (P) ≤
Qℓǫ/2 (P) + O (1/ǫ).
This proposition is often used together with the following known upper bound.
Fact 6. For every family of Boolean functions P, Qℓǫ (P) = O( 1ǫ log |P|).
For the sake of simplicity, we focus on a constant ǫ (say, ǫ = 0.001) throughout the rest of this
paper. This allows us to drop the subscript ǫ from our notation when possible (e.g., we write Q (P)
instead of Qǫ (P)).

1.1

Our results

In [3] it was shown that active testing of dictator functions (i.e., functions that only depend on
a single input variable) requires Θ (log n) queries. Our ﬁrst result extends this to the family of
k-linear functions; that is, the family of sums of k variables over Z2 . Let Link denote this family.
Theorem 7. Active or passive testing of Boolean k-linear functions requires Θ (k log n) queries,
log n
for all k ≤ 10 log
log n .
Theorem 7 and its proof imply a lower bound for active testing of superfamilies of k-linear
functions, such as k-juntas and (n − k)-symmetric functions. A function is called k-junta if it
depends on at most k of its input variables, referred to as the inﬂuential variables (e.g., a dictator
function is a 1-junta). We denote the family of k-juntas by Junk . Partially symmetric functions are
a generalization of juntas, where the remaining variables can inﬂuence the output of the function,
but only in a symmetric manner.
Deﬁnition 8 (Partially symmetric functions [12]). For a subset T ⊆ [n] := {1, . . . , n}, a function
f : Zn2 → Z2 is called T -symmetric if permuting the labels of the variables of T does not change
the function. Moreover, f is called t-symmetric if there exists T ⊆ [n] of size at least t such that f
is T -symmetric. We denote the family of t-symmetric functions by Symt .
Partially symmetric functions were introduced as part of the research of isomorphism testing [12,
14], where it was shown that testing whether a function is (n − k)-symmetric for any k < n/10
can be done using O(k log k) queries. The special case of 2-symmetric functions has already been
considered by Shannon in [25]. In addition to the Ω(k log n) lower bound for active testing of
partially symmetric functions, we provide an upper bound as well as lower and upper bounds for
passive testing (detailed in Table 1). In particular, we show that for a constant k, the family
of partially symmetric functions demonstrates a signiﬁcant gap among the three diﬀerent testing
scenarios and proper learning.
Theorem 9. For a constant k we have
Q Symn−k
Q

a
p

Symn−k





= Θ (1) ,
= Θ (log n) ,
p



= Θ(n1/4 log n),
√

Qℓ Symn−k = Θ( n).

Q

Symn−k

3

The last family of functions considered in this work is low degree polynomials, with special
consideration given to linear functions. The following indicates that passive testing of degree d
polynomials, denoted by Pold , is essentially as hard as properly learning them.
Theorem 10. The query complexity of passive testing of degree d polynomials is Θ(nd ), for constant
d.
On the other hand, active testing can be done slightly more eﬃciently, at least for linear
functions.
Theorem 11. The query complexity of active testing of linear functions is Θ(n/ log n).
Table 1 summarizes the results presented in this work for passive and active testing, as well as
the best known query complexity for the classical model of property testing and proper learning.
Family

Classic (Q)

Active (Qa )

Passive (Qp )

Symmetric
Linear
d-degree
polynomials

O(1)
O(1) [13]

O(1)
Θ(n/ log n)

Θ(n1/4 )
n + Θ(1)

Learning (Qℓ )
√
Θ( n)
n + Θ(1)

Θ(nd )

Θ(nd )

Θ(k log n)

Θ(k log n)

Θ(k log n)

Ω(k log n)

Ω(2k/2 + k log n)

Θ(2k + k log n)

O(2k k log n),
Ω(k log n)

O(n1/4p 2k k log n),
Ω(n1/4 2k + k log n)

k-linear
k-juntas
(n − k)-symmetric

Θ(2d ) [1, 7]
O(k log k),
k − o(k) [9, 11]
O(k log k),
Ω(k)
[9, 10, 15]
O(k log k),
Ω(k) [12]

p

√
Θ( n2k )

Table 1: Summary of best bounds, for ﬁxed ǫ and k < log n/(10 log log n)
The rest of the paper is organized as follows. The lower bound for active testing of k-linear
functions, which applies to juntas and partially symmetric functions as well, is proved in Section 2 by
establishing a general result for random subsets of abelian groups, proved by combining probabilistic
and combinatorial tools including the Talagrand inequality and the Erdős–Rado results on ∆systems. Section 3 provides the lower and upper bounds for active and passive testing of symmetric
and partially symmetric functions, as described in Table 1. The results concerning low degree
polynomials and linear functions in particular are presented in Section 4. Concluding remarks and
open problems are in Section 5. The proofs in Sections 3 and 4 are also based on probabilistic,
combinatorial, and algebraic techniques.

2

k-linear functions

Theorem 7 states that the query complexity of active or passive testing of k-linear functions is
Θ(k log n). The upper bound
can be obtained by applying Propositions 3 and 5, and Fact 6, given

that there are exactly nk diﬀerent k-linear functions.
In order to prove a lower bound for active testing of k-linear functions, we use the following lemma, which is an adaptation of the tools used in [3] to prove active testing lower bounds
(speciﬁcally, Theorem 6.6 and Lemma B.1 ibid).

4

Deﬁnition. A property P is called ǫ-nontrivial if a random Boolean function is ǫ-close to P with
probability at most 0.01.
Lemma 12 ([3]). Let P be an ǫ-nontrivial property of Boolean functions and let π be a distribution
supported on P. Given a set S = {x1 , x2 , . . . , xq } of q queries and a vector y ∈ Zq2 , define
πS (y) = Pf ∼π [f (xi ) = yi for i = 1, 2, . . . , q] .
Choose at random a set U of u samples, and suppose that with probability at least
S ⊆ U of q queries and every y ∈ Zq2 satisfy πS (y) < 65 2−q . Then, Qaǫ (P, u) ≥ q.

3
4,

every set

The proof is based on the fact that, under the assumptions of the lemma, q queries do not
suﬃce to distinguish between a function from the distribution π and a uniform random Boolean
function.
According to Lemma 12, our goal is therefore to show that when we choose a random k-linear
function, querying it at o(k log n) queries chosen from a random space will appear rather random.
To this end we use Lemma 18, which, roughly speaking, assures us that the probability of seeing a
given output vector is very concentrated around the expectation. The proof of the lemma uses the
Talagrand inequality (with an extra twist) and the Erdős–Rado ∆-systems method. Lemma 18, its
proof, and the tools used appear in Section 2.1.
The following theorem provides a lower bound for active testing of k-linear functions, completing
the proof of Theorem 7 (assuming Lemma 18).
Theorem 13. Qa (Link , u) = Ω (k log n) for k ≤ 0.1 log n/ log log n, as long as n ≤ u ≤ 2n

1/7k

.

Proof. Deﬁne π to be the uniform distribution over the k-linear functions. In particular, π is the
distribution obtained by choosing distinct i1 , i2 , . . . , ik ∈ [n] uniformly at random and returning
the function f : Zn2 → Z2 deﬁned by f (x) = xi1 + xi2 + · · · + xik . Fix S to be a set of q vectors
in Zn2 . This set can be viewed as a q × n Boolean-valued matrix. We write c1 (S) , . . . , cn (S) to
represent the columns of this matrix. For any y ∈ Zq2 ,
πS (y) =

n
k

!−1 (

!

X
[n]
I∈
:
ci (S) = y
k
i∈I

)

.

Since Link is, say, 0.4-nontrivial, by Lemma 12, to prove that Qa (Link , u) = Ω (k log n), it
suﬃces to show that when
U is a set of u vectors chosen uniformly and independently at random


from Zn2 and, say, q = 1 − k1 log nk + k, then with probability at least 43 , every set S ⊂ U of size

|S| = q and every y ∈ Zq2 satisfy πS (y) ≤ 65 2−q . To this end, we would like to show that πS (y) is
highly concentrated around E[πS (y)] = 2−q .
1−1/k
To apply Lemma 18, consider the group G = Zq2 and let N = |G| = 2q = 2k nk
. By
1/7k
1/7k
n
⌋ ≥ n and let λ = ⌈qn
⌉ ≥ q log u. Now, for large enough n
monotonicity, we assume u = ⌊2
conditions (3a) and (3b) of the lemma hold. Indeed, to prove the ﬁrst inequality note that
800 ln 2 · kN λ

2k+1

n
= 800 ln 2
k

!1−1/k

k

k2 ⌈qn

1/7k 2k+1

⌉

!1−1/k

n
≤ 800
k

Since k < 0.1 log n/ log log n and q < 2k log n < (log n)2 , we have
800(2qn

1/7k 2k+1

)

√
= o( n) < n/k <
5

!1/k

n
k

.

· (2qn1/7k )2k+1 .

(1)

Therefore, the right-hand-side of (1) is smaller than
To prove the second inequality note that
λ
λN
=
k2k

n1−1/k
k

k

≥

However,

qn1/7k

n
k

n1/k
k
k

(n − k + 1)qn1/7k
k

n1/k
k
k

=

≥Ω

n
k ,

establishing (3a).

(n − k + 1)qn1/7k
k



n1/k
k
k

nk log n
nk



!

n
.
k−1

(2)

> 1,



n
and therefore the right-hand-side of (2) is bigger than k−1
, proving (3b).

Thus, for any ﬁxed vector y ∈ Zq2 , the probability that more than 56 nk 2−q k-sets of columns of
S sum to y is at most 5 · 2−λ . Furthermore, when U is deﬁned as above, we can apply the union
bound over all y ∈ G and over all subsets S ⊆ U of size |S| = q to obtain





6
P ∃S, y : πS (y) > 2−q ≤
5

!

u
uq q
· 2 · 5 · 2−q log u = o (1) ,
· 2q · 5 · 2−λ ≤
q!
q

establishing the theorem.
The above theorem and its proof immediately imply a lower bound for active testing of both
k-juntas and (n − k)-symmetric functions. This can also be applied to show lower bounds for other
concise representation families, such as small DNF formulas, small decision trees, small Boolean
formulas, and small Boolean circuits (see [17]).
Corollary 14. Qa (Junk ) = Ω(k log n) and Qa (Symn−k ) = Ω(k log n) for k = O (log n/ log log n).
Proof. The same distribution π from the proof of Theorem 13 (uniform distribution over the klinear functions) is supported on k-juntas (resp., (n − k)-symmetric functions) and these properties,
too, are still 0.4-nontrivial.
In Section 3 we continue the investigation of active and passive testing of partially symmetric
functions. The following proposition summarizes what we know about passive testing of k-juntas.




Proposition 15. Ω(2k/2 + k log n) ≤ Qp (Junk ) ≤ O 2k + k log n .
Proof. The upper
bound is obtained by applying Proposition 5 and Fact 6, as the number of
 k
k-juntas is nk 22 . The lower bound is a combination of two separate bounds:2 Ω (k log n) by
Corollary 14 and Ω 2k/2 for verifying that the input function is indeed a junta, even when the set
of the inﬂuencing variables is known in advance. Indeed, assume we are given the input function
with a promise that it is either a random junta over the ﬁrst k variables or a random function.
Distinguishing between these two cases is impossible unless we have a pair of inputs agreeing on
the ﬁrst k variables; among less than 12 2k/2 queries, we get such a pair with probability at most
1
2



1 k/2
22

2.1

2

· 2−k = 1/8.

Proof of main lemma

Before we state the formal lemma, we introduce the two following combinatorial and probabilistic
tools used in the proof.
2
Although Corollary 14 only holds for k = O(log n/ log log n), for larger values of k its contribution to the lower
bound is negligible.

6

Erdős–Rado ∆-systems
Deﬁnition. Let a, b be positive integers. We say that a family of a sets, each of size b, forms a
∆-system of size a if all pairs have the same intersection.
Erdős and Rado proved that every large enough family of sets contains a large ∆-system.
Theorem 16 ([18, Theorem 3]). Let F be a family of sets, each of size b. Then F contains
∆-system of size a whenever |F| ≥ (a − 1)b+1 b!.
Talagrand’s concentration inequality
In its general form, Talagrand’s inequality is an isoperimetric inequality for product probability
spaces. We use the following formulation from [23] (see also [2, 26]), suitable for showing that a
random variable in a product space is concentrated around its expectation under two conditions:
Theorem 17 ([23, page 81]). Let X ≥ 0 be a non-trivial random variable, determined by n
independent trials T1 , . . . , Tn . If there exist c, r > 0 such that
(i) X is c-Lipschitz: changing the outcome of one trial can affect X by at most c, and
(ii) X is r-certifiable: for any s, if X ≥ s then there is a set of at most rs trials whose outcomes
certify that X ≥ s,
then for any 0 ≤ t ≤ E [X],

where τ = c2 rE [X].



√ 

P |X − E [X]| > t + 60 τ < 4 exp −t2 /8τ ,

We now state the main lemma.
Lemma 18. Let G be an abelian group of order N , and let n ∈ N. Consider a random sequence
X = (x1 , x2 , . . . , xn ), where each xi ∈ G is chosen uniformly and independently
at randomo (with
n
 P
repetitions). Fix y ∈ G and k ∈ N, and let Y = |Y|, where Y = I ∈ [n]
:
i∈I xi = y . Let
k
λ ≥ 2 log N be a positive integer and assume that
n
k

!

≥ 800 ln 2 · kN λ2k+1 ; and

!

n
λN
≤ k.
k2
k−1
Then,

(3a)
(3b)





1
P |Y − E [Y ]| > E [Y ] < 5 · 2−λ .
5

Proof. For k = 1 we have Y ∼ Bin (n, 1/N ) and the result is implied by Chernoﬀ’s inequality,
so we henceforth assume k ≥ 2. We would like to use Talagrand’s inequality to prove that Y
is concentrated around E [Y ], but Y does not satisfy the Lipschitz condition necessary for its
application. Let us thus deﬁne Ŷ = Ŷ , where Ŷ ⊆ Y is maximal such that, for all j ∈ [n], xj

belongs to at most c sets I ∈ Ŷ; the exact value of c will be determined later.
7

n

[n]\{j}
k−1

First we bound the probability that Ŷ 6= Y . Let Yj = I ∈
rem 16, there exists a ∆-system Zj ⊆ Yj of size
|Zj | ≥ 1 +

o

: I ∪ {j} ∈ Y . By Theo-

q
k

|Yj | / (k − 1)! > |Yj |1/k e/k,

where every two distinct I1 , I2 ∈ Zj have the same intersection Kj = I1 ∩ I2 . Thus, Zj′ =
P

{I \ Kj : I ∈ Zj } is a collection of sj = Zj′ = |Zj | disjoint k′ -sets such that i∈I xi = z for
P
all I ∈ Zj′ , where k′ = k − 1 − |Kj | ≤ k − 1 and z = y − xj − i∈Kj xi .
Consider the event Ez (s), deﬁned as the existence of a collection of s disjoint k′ -subsets of X
that all sum to the same element z ∈ G. Then,
!

n
1 n
P [Ez (s)] ≤
N −s ≤
s! k′
k′ , k′ , . . . , k′
|

{z
s

}

!s

N

−s

n
e
sN k − 1

≤

!!s

≤



eλ
sk2k

s

,

and thus we have, for the choice of c = λk ,
h

i

h

P Y > Ŷ ≤ P [∃j ∈ [n] : |Yj | > c] ≤ P ∃j ∈ [n] : sj > c1/k e/k


≤ P [∃z ∈ G : Ez (eλ/k)] ≤ N 2−k

eλ/k

i

(4)

= 2log N −eλ < 2−2λ .

This also serves to show that E [Y ] and E[Ŷ ] are very close, since
!

!2



2

1
λ2 2−λ
< .
64
32
(5)
Next we apply Talagrand’s inequality to bound the deviation of Ŷ from E[Ŷ ]. By deﬁnition,
Ŷ is c-Lipschitz; moreover, to prove that Ŷ ≥ s we only need to reveal s k-sets, i.e., reveal xi for
P
at most ks values of i. For every choice of I ∈ [n]
i∈I xi is a random element of G and thus
k ,
E [Y ] = nk /N ≥ 800 ln 2 · kλ2k+1 .
Set τ = c2 kE[Ŷ ]. By Theorem 17,
h

i





h

i

E Y − Ŷ ≤ max Y − Ŷ ·P Y > Ŷ ≤



P Ŷ − E[Ŷ ] >



n −2λ
2
≤
k

n
k−1



√
1
E[Y ] + 60 τ ≤ 4 exp −E[Y ]2 /800τ
10




2−2λ ≤

λN
k2k



2−2λ ≤



≤ 4 exp −E[Y ]/800c2 k < 4 exp −λ2k+1 ln 2/c2 = 4 · 2−λ .
(6)

Putting (4), (5) and (6) together,








h
i
1
1
P |Y − E [Y ]| > E [Y ] ≤ P Y > Ŷ + P Ŷ − E [Y ] > E [Y ]
5
5


h i
1
1
−λ
≤ 2 + P Ŷ − E Ŷ > E [Y ] −
< 5 · 2−λ ,
5
32
√
1
1
≥ 10
E [Y ] + 60 τ , satisﬁed whenever λ ≥ 650.
under the condition 15 E [Y ] − 32

3

Partially symmetric functions

A key concept in the study of symmetric and partially symmetric functions is the following notion:
8

Deﬁnition ([12, Deﬁnition 3.1]). The symmetric inﬂuence of a set T ⊆ [n] of variables in a Boolean
function f : Zn2 → Z2 is deﬁned as
SymInf f (T ) = Px∈Zn2 ,σ∈Sn [f (x) 6= f (σ (x)) | ∀i 6∈ T : σ (i) = i] .
By deﬁnition, a T -symmetric function f has SymInf f (T ) = 0; conversely, for functions far from
being T -symmetric we have the following lemma:
Lemma 19 ([12, Lemma 3.3]). If f is ǫ-far from being T -symmetric, then SymInf f (T ) ≥ ǫ.
In other words, distinguishing between a T -symmetric function and one far from being T symmetric can be done by estimating the symmetric inﬂuence.
The following proposition determines the number of queries needed for passive and active testing
of symmetric Boolean functions. Although these results are a special case of partially symmetric
functions, we feel that this serves as an introduction and provides some intuition.
Proposition 20. Qp (Symn ) = Θ(n1/4 ) and Qa (Symn ) = O(1).
Proof. A symmetric function is characterized by its layers of diﬀerent Hamming weight. For each
Hamming weight between 0 and n, the function outputs a consistent value. To test symmetry given
a function, it suﬃces to randomly choose an input x ∈ Zn2 and a permutation of it, and see if the
output is consistent over the two inputs. Since the Hamming weight of x is distributed
Bin (n,
p 1/2),

two random inputs share the same Hamming weight with probability 4−n 2n
=
(1
+
o
(1))
2/πn;
n
1 1/4
having fewer than 2 n
random samples yields even a single such pair with probability at most
1
2



1 1/4
2n

2 p

·

2/πn < 1/8.

On the other hand, among 4 (2πn)1/4 random samples, it is not hard to see that the probability
of not having such a pair is smaller than, say, 1/7. (One way to show this fact is by looking for
matches between the ﬁrst and second halves of the samples, assuming the ﬁrst half did not yield
such a pair already. In this case with high probability the total measure of the layers in which we
1
have a representative from the ﬁrst half is at least (2πn)
1/4 and conditioning on this, the probability
that no sample from the second half falls into one of these layers is smaller than e−2 .)
By Markov, repeating this 14/ǫ times results in at least 12/ǫ sets without a desired pair with
probability at most 1/6. Therefore, with probability at least 5/6, we have at least 2/ǫ pairs. By
Lemma 19, if the function is ǫ-far from being symmetric then each such pair will have diﬀerent
outputs with probability at least ǫ, so we will fail to detect this with probability (1 − ǫ)2/ǫ < 1/e2 .
Altogether the success probability exceeds 2/3.
In the context of active testing, given a sample space of, say, u = n/ǫ vectors we can easily ﬁnd
2/ǫ input pairs with the same Hamming weight each, thus testing whether the input function is
indeed symmetric can be done using 4/ǫ queries.
Remark. Consider the following slight modiﬁcation of the algorithms above. Instead of rejecting
the input function upon the ﬁrst example of it not being symmetric, we estimate its symmetric
inﬂuence by counting the number of such examples among all pairs. This enables us to passively
(resp., actively)distinguish
that is ǫ/2-close to being symmetric and one that
 between a function

−2
1/4
−2
is ǫ-far using O ǫ n
(resp., O ǫ ) queries. Such an algorithm is called a tolerant tester.

Some families of Boolean functions, such as symmetric and partially symmetric functions, have
many pairs of functions which are close to one another. In these cases, the upper bound of Fact 6,
which relies only on the size of the family, is not tight. We remedy this by proving the following
reﬁned version.
9

Deﬁnition 21. Let P be a family of Boolean functions and let ǫ > 0. Denote by Iǫ (P) a subfamily
of P of maximal size such that every two distinct f, g ∈ Iǫ (P) are ǫ-far.
Proposition 22. Let P be a family of Boolean functions and let ǫ > 0. Then
⌊log |I2ǫ (P)|⌋ ≤ Qℓǫ (P) ≤

l

64
ǫ

m

ln Iǫ/2 (P) .

Proof. A proper learning algorithm for P is required to return a function from P that is ǫ-close
to the input function. Since functions in I2ǫ (P) are 2ǫ-far from one another, the algorithm has
to return a diﬀerent output for each of them. Any deterministic algorithm making q queries
can only have 2q diﬀerent outputs, so if it performs less than ⌊log |I2ǫ (P)|⌋ queries, it must be
wrong with probability at least 1/2. A randomized algorithm for this problem can be viewed as a
distribution over deterministic algorithms (as the queries are chosen randomly and the algorithm
is non-adaptive), and therefore cannot improve the success probability beyond 1/2.
Next, consider the following learning algorithm: given an input function f ∈l P, return the funcm
tion g ∈ Iǫ/2 (P) that agrees with f on as many queries as possible out of q = (64/ǫ) ln Iǫ/2 (P)
random queries. By deﬁnition, f is ǫ/2-close to some f ′ ∈ Iǫ/2 (P); therefore, f and f ′ disagree on
each query with probability at most ǫ/2, independently. The total number of disagreements is thus
dominated by a Bin (q, ǫ/2) random variable and hence with high probability they disagree on fewer
than 3ǫq/4 queries. Using a similar argument, a function h ∈ Iǫ/2 (P) that is ǫ-far from f will dis−2

agree with f on more than 3ǫq/4 queries with probability at least 1−exp (−ǫq/32) = 1− Iǫ/2 (P) .
By the union bound, with high probability no such h will outperform f ′ and thus the algorithm
will return a function that is ǫ-close to f (the obvious candidate being f ′ ).
√
√
Corollary 23. Qℓ (Symn−k ) = Θ(2k n − k) for k < n; in particular, Qℓ (Symn ) = Θ( n).
Proof. First, we show that Iǫ/2 (Symn−k ) = 2O(2

k

√
n−k )

. The binomial distribution Bin (n − k, 1/2)
m

lp

is concentrated around its center, and in particular the middle ℓ = 1 + 2
(n − k) ln (4/ǫ) /2 layers account for at least 1 − ǫ/2 of the weight. In other words, every (n − k)-symmetric function is
(ǫ/2)-close to an ℓ-canonical (n − k)-symmetric function, which is zero outside the middle ℓ layers.
k
We can thus bound Iǫ/2 (Symn−k ) from above by 22 ℓ , the number of ℓ-canonical functions.
j√
k
For the lower bound, consider the middle ℓ′ = 1 + 2 n − k layers. The weight ratio between
n−k 
⌊(n−k)/2⌋ /



k ′

n−k√
2
2 ℓ
⌊(n−k)/2− n−k⌋ < e . Let C ⊂ Z2 be an
k−1 ′
error correcting code of rate 1/2 and relative distance 1/10; in other words, C has at least 22 ℓ
codewords, every pair of which are (1/10)-far. We can interpret each codeword as an ℓ′ -canonical
(n − k)-symmetric function, which is 1/10e2 -far from the rest. Hence we get I2ǫ (Symn−k ) ≥
k−1 ′
22 ℓ as long as ǫ < 1/20e2 .
Therefore, for our ﬁxed ǫ, the result follows from Proposition 22.

any pair of these layers is bounded by

Proposition 25 provides an upper bound for the query complexity of passive and active testing
of partially symmetric functions. Its proof relies on the following simple concentration claim in
which we make no attempt to optimize the estimates.
Claim 24. There is an absolute constant b > 0 such that for every c, 0 < c < 1 the following
holds. Let s and t be integers satisfying s < t. Let P be an arbitrary probability distribution on t
bins, where the probability of each bin is at least c/t. Then, when we throw s balls randomly and

10

independently into t bins according to the probability P , the probability of getting less than cs2 /9t
collisions3 is at most exp −bcs2 /t .

Proof. If the number of occupied bins is less than s/3 after ⌈s/2⌉ balls were thrown, then we already
have at least s/6 > cs2 /9t collisions. Otherwise, each of the next ⌊s/2⌋ balls has a probability of at
least cs/3t to collide with these occupied bins, independently. The number of collisions created by
the last ⌊s/2⌋ balls thus dominates a binomial Bin (⌊s/2⌋, cs/3t) random variable. By Chernoﬀ, it
is less than cs2 /9t with probability at most exp −bcs2 /t .





√
Proposition 25. Qp (Symn−k ) = O n1/4 2k/2 k log n and Qa (Symn−k ) = O 2k k log n , for k =
o (log n).

Proof. We begin with a passive√testing algorithm. Let f be the tested Boolean function. Our
algorithm asks q = d(ǫ)n1/4 2k/2 k log n queries, and if the results obtained are consistent with f
being (n − k)-symmetric it accepts, otherwise it rejects. It remains to show that if f is ǫ-far from
being (n − k)-symmetric the algorithm rejects with high probability. Assume this is the case and

ﬁx a k-set T ∈ [n]
k of variables. If we choose a random vector x and another random vector y
obtained from x by permuting the elements in [n] \ T the probability that f (x) 6= f (y) is at least
ǫ by Lemma 19. By Claim 24 (where each bin corresponds to the ordered pair consisting of the
√
projection on T and the Hamming weight of a typical vector, which is within distance Θ( n) from
n/2), for an appropriately chosen d(ǫ), with probability at least 1 − n−k our queries will contain
2
more than 0.5 d(ǫ)
9 k log n > k log n/ǫ random disjoint pairs x, y which have the same Hamming
weight and agree on T . The probability that none of these pairs will satisfy f (x) 6= f (y) is at most
(1 − ǫ)k log n/ǫ < n−k . The union bound thus completes the argument.


The same argument implies that the query complexity of active testing is O 2k k log n because
√
the only queries
the passive algorithm above actually used are the results for the Θ(q 2 / n) =

Θ 2k k log n pairs x, y which agree on their Hamming weight. The active algorithm will thus




simply select from the sample Θ 2k k log n disjoint pairs with the same Hamming weight and
proceed as the passive algorithm.
The following proposition provides a lower bound for the query complexity of passive testing
of partially symmetric functions. Note that it matches the upper bound, up to a constant factor,
when k is constant.



√
Proposition 26. Qp (Symn−k ) = Ω n1/4 2k/2 + k log n .

Proof. As in the proof of Proposition 15, we use a combination of two lower bounds. The ﬁrst one,
Ω(n1/4 2k/2 ), is required even when the identity of the k asymmetric variables is known in advance.
Assuming we are given the promise that the input function is either (n − k)-symmetric and the
asymmetric variables are the ﬁrst k variables, or it is far from being partially symmetric, one still
needs to verify the partial symmetry. The only way to verify it is by having pairs of inputs that
share Hamming weight and agree on the values
of the

 ﬁrst k variables. However, we expect to see
no such pairs if the number of queries is o n1/4 2k/2 .
The second part of the lower bound uses the Ω(k log n) bound of Theorem 13. We wish to show
that distinguishing the sum of a random k-linear function
a random
 symmetric function cannot
 and
√
be distinguished from a random function, given q = o n1/4 k log n queries. Indeed, assume this
3

A single collision happens every time we place a ball in an already occupied bin.

11

many queries were performed and denote by H ⊆ {0, 1, . . . , n} the set of Hamming weights attained
by at least two queries. A balls and bins argument shows that we expect only o (k log n) queries
whose Hamming weight lies in H. Due to the random symmetric function, the algorithm cannot
extract any information from queries that have a unique Hamming weight. Say that we reveal to
the algorithm the value of the random symmetric function on H. Now, the algorithm has o(k log n)
queries and it must distinguish between a k-linear function and a random function. Even if the
algorithm were allowed to choose which queries to pick out of the initial set of q queries, the lower
bound for active testing of k-linear functions indicates this cannot be done.
Theorem 9 follows from Propositions 25 and 26 and Corollaries 14 and 23, as well as the results
of [12].

4

Low degree polynomials


P



n
We prove Theorem 10 for a more general case, allowing 1 ≤ d ≤ n1/3 . Let ≤d
= di=0 ni be the
n
number of monomials of degree at most d. Note that for constant d, we have ≤d
= Θ(nd ).

Theorem (Restatement of Theorem 10). Qp (Pold ) = Θ(

n
≤d ).

n
(≤d
) , hence by Fact 6 and Proposition 5, passive
Proof. The number of polynomials
of
degree
d
is
2

n
n
) queries. We now show a lower bound of Ω( ≤d
) queries.
testing can be done using O( ≤d

j



k

n
/2e random queries performed by a passive
Let x1, x2, . . . , xq ∈ Zn2 be the set of q = ≤d
n
( )
tester. For i = 1, . . . , q, deﬁne yi ∈ Z2≤d to be the d-evaluation of xi , that is, the evaluations of
all possible monomials of degree at most d at xi . It suﬃces to show that {yi } qi=1 are most likely
n
linearly independent to conclude that any testing algorithm performs badly; indeed, since the ≤d
q
monomials serve as a basis to Pold , {yi } i=1 being linearly independent implies that every possible
output (f (x1 ), . . . , f (xq )) ∈ Zq2 is equally likely when choosing a random f ∈ Pold , so the tester
sees a uniform distribution and therefore cannot decide.
In order to show that, with high probability, these vectors are linearly independent, we bound
the probability that yi is spanned by y1 , . . . , yi−1 , and then apply the union bound to show that
none of these events is likely to occur. Let Vi = span {y1 , . . . , yi−1 } be the linear space spanned by
the ﬁrst i − 1 vectors. By Lemma 4 from [6], since

dim Vi ≤ i − 1 < q ≤

!

!

d
X
n
⌈n(1 − 1/d)⌉
/2e ≤
,
≤d
i
i=0

no more than 2⌈n(1−1/d)⌉ d-evaluations of vectors from Zn2 reside in Vi . Thus, P [yi ∈ Vi ] ≤ 2−⌈n/d⌉
and, by the union bound, P [∃i : yi ∈ Vi ] ≤ q · 2−⌈n/d⌉ = o(1) for d ≤ n1/3 .
We now focus on linear functions, for which we determine the passive query complexity up to
an additive constant term. We slightly abuse notation by using Pol1 to denote the family of linear
functions, even though degree 1 polynomials include both linear and aﬃne functions.
Proposition 27. Qp (Pol1 ) = n + Θ(1).
Proof. As in the proof of Theorem 10, a linearly independent query set is useless for the testing
algorithm. Let x1, x2, . . . , xq be a sequence of q ≤ n queries and deﬁne Xi to be the event that
12

xi ∈ span {x1 , . . . , xi−1 }. The probability that some linear dependency exists among the q queries
is
P

"

q
[

i=1

#



Xi = P 

q
[

i=1



Xi \

i−1
[

j=1



Xj  =

q
X
i=1



P Xi \

i−1
[

j=1



Xj  ≤

q
X

2i−1−n =

i=1

2q − 1
.
2n

For q > n, surely any set of q queries is linearly dependent.
Given the computation above, a set of q ≤ n−2 queries is expected to be linearly dependent with
probability smaller than 1/4. On the other hand, n + O(1) queries are very likely to provide a basis
for Zn2 and O (1) linear dependencies, so we can learn the unique linear function consistent with
the basis and then verify it; if the function is ǫ-far from linear, each additional query is inconsistent
with the learned function with a constant probability.
Active testing allows us to reduce the query complexity by a logarithmic factor, in comparison
to passive testing. We ﬁrst prove the following lemma, which is an extension of the analysis of the
BLR test provided by Bellare et al. [4].
Lemma 28. Given a function f : Zn2 → Z2 that is ǫ-far from being linear,
Px1 ,x2 ,...,x2k ∈Zn2 [f (x1 ) + · · · + f (x2k ) = f (x1 + · · · + x2k )] ≤

1
2

+ 12 (1 − 2ǫ)2k−1

P
P
Proof. Since f is ǫ-far from being linear, when writing it in the Fourier basis f (y) = S⊆[n] fˆ (S) i∈S yi
all of its Fourier coeﬃcients {fˆ(S) : S ⊆ [n]} are bounded from above by 1 − 2ǫ. Similar to the
analysis for the case k = 1, the success probability of this test is:
1
1
2+2

X

S⊆[n]

fˆ(S)2k+1 ≤ 12 + 12

max fˆ(S)2k−1

S⊆[n]

!

X

S⊆[n]

fˆ(S)2 = 21 + 12 max fˆ(S)2k−1 ≤ 12 + 21 (1−2ǫ)2k−1 ,
S⊆[n]

where the middle equality holds by Parseval’s theorem.
Unlike the BLR test, which uses the case k = 1, in the context of active testing we need k to
be almost linear in n, hence little ampliﬁcation is necessary.
Theorem (Restatement of Theorem 11). Qa (Pol1 , u) = Θ(n/ log u), for u ≥ n2 .

Proof. As done in the previous proof, we bound the number of queries from below by showing that
one is not expected to ﬁnd a linear dependency of size smaller than n/(2 log u) among a set of u
samples. The expected number of linear dependencies of size at most q is at most
q
X
u
i=0

i

!

2−n ≤ uq 2−n = 2q log u−n ≤ 2−n/2 ,

assuming q ≤ n/(2 log u). By Markov’s inequality, the probability of having such a linear dependency is o (1) and therefore Ω( logn u ) queries are needed.
Given an input function that is ǫ-far from being linear, we use the test of Lemma 28 to identify
u
this. Fix q = 4 ⌈n/ log u⌉. Given a sample U of u vectors, it contains q/2
> 2n subsets of size q/2.
By the pigeonhole principle two of these sets have the same sum, hence there is a linear dependency
of length at most q. On the other hand, by the previous computation, with high probability there is
no linear dependency of size less than n/(2 log u) = q/8 hence the length exceeds q/8. By Lemma 28
the probability that f passes a single such test is at most 12 + 12 (1 − 2ǫ)q/8−1 < 21 + 12 (1 − 2ǫ)n/2 log u .
Since ǫ is constant, for large enough n this is smaller than 0.9, thus repeating the test a constant
number of times reduces the probability of f passing all of them to less than 1/3 (obviously we
never reject a linear function).
13

5

Discussion

Throughout this work we have demonstrated new bounds for the number of queries needed for
active and passive testing of several properties. In particular, we now know the amount of queries
needed for testing k-linear functions in these new models.
A practical aspect of property testing algorithms that we did not cover is the actual running
time, rather than just the number of queries performed, which was the only concern in this work.
Some of the algorithms we presented, especially those based on proper learning, have an exponential
run-time complexity and it would be interesting to see whether active or passive testing can be
done while maintaining polynomial running time.
Quite a few of the passive testing algorithms we provided can in fact be made tolerant; that is,
they can be modiﬁed to accept functions close to satisfying the property while rejecting functions
far from satisfying it (with some gap in between). For simplicity we did not explicitly show that.
Such modiﬁcations usually do not have an eﬀect on the asymptotic query complexity.
While Section 4 provides a tight analysis of active and passive testing of linear functions, for
low degree polynomials our analysis is only tight for passive testing. Extrapolating based on the
behavior of linear functions, it seems natural to expect that the query complexity of active testing of
low degree polynomials is asymptotically lower than passive testing, perhaps by a polylogarithmic
factor. This question remains open at the moment.
Finally we mention that Lemma 18, used in the proof of Theorem 13, can be used in the study
of a seemingly unrelated problem of exhibiting a very sharp cutoﬀ phenomenon in the mixing time
of random walks in random (dense) Cayley graphs of abelian groups. Indeed, the lemma implies
that for any abelian group G of order N , and for (log N )1/3 ≤ k ≤ (log N )1/2−δ , if we choose
d ≈ N 1/(k−1) random elements of G, then a random walk of length k − 1 in the resulting Cayley
graph of G is far from being mixing (simply because we cannot reach most of the elements at
all) while a random walk of length k is already mixing. While it is more interesting to study this
problem for much sparser random Cayley graphs (see [22] for some related results), even the above
statement for the dense case is interesting.

References
[1] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron, Testing lowdegree polynomials over GF(2). In: Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 7th International Workshop
on Randomization and Approximation Techniques in Computer Science (RANDOM–APPROX
’03), pp. 188–199, 2003.
[2] Noga Alon and Joel H. Spencer, The Probabilistic Method (3rd Edition). Wiley, New York,
2008.
[3] Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang, Active property testing. In:
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS
’12), pp. 21–30, 2012.
[4] Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos Kiwi, and Madhu Sudan, Linearity
testing in characteristic two. IEEE Transactions on Information Theory 42(6): 1781–1796,
1996.

14

[5] László Babai, Lance Fortnow, and Carsten Lund. Nondeterministic exponential time has twoprover interactive protocols. Computational Complexity 1(1):3–40, 1991
[6] Ido Ben-Eliezer, Rani Hod, and Shachar Lovett, Random low-degree polynomials are hard to
approximate. Computational Complexity 21(1): 63–81, 2012.
[7] Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman, Optimal testing of Reed-Muller codes. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS ’10), pp. 488–497, 2010.
[8] Eric Blais, Improved bounds for testing juntas. In: Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 12th International Workshop on Randomization and Approximation Techniques in Computer Science
(RANDOM–APPROX ’08), pp. 317–330, 2008.
[9] Eric Blais, Testing juntas nearly optimally. In: Proceedings of the 41st Annual ACM Symposium
on Theory of Computing (STOC’ 09), pp. 151–158, 2009.
[10] Eric Blais, Joshua Brody, and Kevin Matulef, Property Testing Lower Bounds via Communication Complexity. Computational Complexity 21(2):311–358, 2012.
[11] Eric Blais and Daniel Kane, Tight bounds for testing k-linearity. In: Proceedings of the 15th
International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 16th International Workshop on Randomization and Approximation Techniques in
Computer Science (RANDOM–APPROX ’12), pp. 435–446, 2012.
[12] Eric Blais, Amit Weinstein, and Yuichi Yoshida, Partially symmetric functions are eﬃciently
isomorphism-testable. Proceedings of the 53rd Annual IEEE Symposium on Foundations of
Computer Science (FOCS ’12), pp. 551–560, 2012. Also: SIAM J. on Computing 44(2):411–
432, 2015.
[13] Manuel Blum, Michael Luby, and Ronitt Rubinfeld, Self-testing/correcting with applications
to numerical problems. In: J. of Computer and System Sciences 47:549–595, 1993.
[14] Sourav Chakraborty, Eldar Fischer, David García–Soriano, and Arie Matsliah, Juntosymmetric functions, hypergraph isomorphism, and crunching. In: Proceedings of the 27th
Annual IEEE Conference on Computational Complexity (CCC ’12), pp. 148–158, 2012.
[15] Hana Chockler and Dan Gutfreund, A lower bound for testing juntas. Information Processing
Letters 90(6):301–305, 2004.
[16] David Cohn, Les Atlas, and Richard Ladner, Improving generalization with active learning. In:
Proceedings of the 15th International Conference on Machine Learning (ICML ’94), pp. 201–
221, 1994.
[17] Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, and Andrew Wan. Testing for concise representations. In: Proceedings of the 48th Annual
IEEE Symposium on Foundations of Computer Science (FOCS ’07), pp. 549–558, 2007.
[18] Paul Erdős and Richard Rado, Intersection theorems for systems of sets. J. London
Math. Soc. 35(1): 85–90, 1960.

15

[19] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky, Testing juntas.
J. of Computer and System Sciences 68(4):753–787, 2004.
[20] Oded Goldreich, Shaﬁ Goldwasser, and Dana Ron, Property testing and its connection to
learning and approximation. J.of the ACM 45(4):653–750, 1998.
[21] Michael Kearns and Dana Ron, Testing problems with sublearning sample complexity. J. of
Computer and System Sciences 61(3):428–456, 2000.
[22] Eyal Lubetzky and Allan Sly, Cutoﬀ phenomena for random walks on random regular graphs.
Duke Mathematical Journal 153(3):475–510, 2010.
[23] Michael Molloy and Bruce Reed, Graph colouring and the probabilistic method,
Springer, 2002.
[24] Ronitt Rubinfeld and Madhu Sudan, Robust characterizations of polynomials with applications
to program testing. SIAM J. on Computing 25(2):252–271, 1996.
[25] Claude E. Shannon, The synthesis of two-terminal switching circuits. Bell System Technical
Journal 28(1):59–98, 1949.
[26] Michel Talagrand, Concentration of measure and isoperimetric inequalities in product spaces.
Publications Mathématiques de l’IHÉS 81:73–203, 1995.
[27] Leslie G. Valiant, A theory of the learnable. Communications of the ACM 27(11):1134–1142,
1984.

16

