Testing juntas.
We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of queries that depends only polynomially on J and the approximation parameter . We present several tests that require a number of queries that is polynomial in J and linear in -1. We showa non-adaptive tests that has one-sided error, an adaptive version of it that requires fewer queries, and a non-adaptive two-sided version of the test that requires the least number of queries. We also show a two-sided non-adaptive test that applies to functions over n boolean variables, and has a more compact analysis.We then provide a lower bound of (J) on the number of queries required for the nonadaptive testing of the above property; a lower bound of (log(J + 1)) for adaptive algorithms naturally follows from this. In establishing this lower bound we also prove a result about random walks on the group Z2q that may be interesting in its own right. We show that for some the distributions of the random walk at times t and t are close to each other, independently of the step distribution of the walk.We also discuss related questions. In particular, when given in advance a known J-junta function h, we show how to test a function f for the property of being identical to h up to a permutation of the variables, in a number of queries that is polynomial in J and -1.
Introduction
Combinatorial property testing deals with the following task: For a xed
property P and any given input f , one has to distinguish with high probability
between the case where f satises P and the case where f is 'far' from
satisfying it, accessing the least possible number of bits from the input.
A property P is said to be -testable using q queries, or simply (; q)-
testable, if there exists a probabilistic algorithm that makes at most q queries
on any given input f (it is assumed that the input is accessed using an
oracle), such that
if f satises P , then the algorithm accepts it with probability at least
2=3, and
if f is -far from P , that is, if it must be changed in more than an -
fraction of the places in order to make it satisfy P , then the algorithm
rejects it with probability at least 2=3.
A testing algorithm is said to be 1-sided if it accepts with probability
any input that satises P . A testing algorithm that determines all its
queries in advance, and uses the answers only in deciding whether to accept
the input (and not in planning some of the queries) is called a non-adaptive
test.
The general notion of property testing was rst formulated by Rubinfeld
and Sudan [21], who were motivated mainly by its connection to the study
of program checking. The study of this notion for combinatorial objects,
and mainly for graphs, was introduced by Goldreich, Goldwasser and Ron
[14].
Property testing has recently become a very active research area, see for
example the surveys [20] and [10]. In addition to its theoretical appeal, it
emerges in the context of PAC learning [14], program checking [21], probabilistically
checkable proofs [3, 4], approximation algorithms [14] and more.
Properties of Boolean functions were given particular consideration from the
point of view of property testing, and especially properties related to monotonicity
[13, 9, 11]. Perhaps the work most closely related to ours is [19]. In
that work testing algorithms that perform O(1=) queries are described for
the following properties of Boolean functions: Being a singleton function (a
function of a single variable), being a k-monomial (a conjunction of at most
k literals), and being a monotone DNF function with a bounded number of
terms.
1.1 Preview of results
In this paper we consider properties of Boolean functions over n Boolean
variables. Throughout the paper we use the f0; 1g notation for Boolean
domains and the f1; 1g notation for Boolean ranges. Thus, we consider
functions of the 1g. Specically, we concern ourselves
with the property that a Boolean function depends on only k (or less)
of its variables. Some notation: for
and
Denition 1 (a junta, a dominating set). A Boolean function f :
is called a k-junta if there exists a set J  [n] of size
at most k, and a Boolean function 1g, such that
In this case it is said that f is dominated by J . Somewhat abusing notation,
J is also referred to as the junta that dominates f .
Knowing that a function depends on only a small number of variables can
be especially useful in the context of learning. For various functions classes
there exist algorithms that are attribute e-cient (cf. [16, 5, 6, 22]). That is,
they have polynomial dependence on the number of relevant variables of the
function being learned but only logarithmic dependence on the total number
of variables. One should also mention here the work of [18] concerning
computationally e-cient learning of such functions when the algorithm is
restricted to uniform samples.
As part of this eort, [15] presented an algorithm, that for any input
function f , uses O(k(log(k log n)) queries to completely determine
a k-junta that dominates a function f 0 that is -close to f , if such a k-junta
exists. In particular, their algorithm can be used to test for the property
of being a k-junta. We show here the possibility of constructing a test for
being a k-junta whose number of queries does not depend on n at all.
Theorem 1 (the main result). For every xed k the property of being a
k-junta is (; poly(k)=))-testable for any given .
In order to establish Theorem 1 we describe two testing algorithms.
The rst algorithm is non-adaptive, requires O(k 4
is stronger in that it is 1-sided. We also provide an adaptive variant of
this algorithm which requires only O(k 3 queries, and a non-adaptive
variant with a 2-sided error which also requires only O(k 3
1)=) queries; we also describe possibilities for some further improvements.
The second algorithm is non-adaptive, has query complexity O(k 4
1)=), and a 2-sided error. However, it yields to a more compact analysis.
On the other hand, at least with regards to non-adaptive algorithms, we
show that the dependency has to be a power of k (the tilde notation in the
following is used to hide polylogarithmic factors).
Theorem 2. For every  > 0, a non-adaptive 1
-test for the property
of being a k-junta requires at least q
~
queries.
Recently, Chockler and Gutfreund [7] have proven a better lower bound,
which holds for adaptive testing algorithms as well. However, the proof
given here may have signicance beyond the lower bound itself, since during
its course we prove a result about random walks on the group Z q
2 that may
be of an independent interest.
Given any (nite) group G and a distribution P on G, a random walk
on G with step distribution P starts with the identity element, and at each
step t, denoting its current position by X t , picks a random element  t of G
according to P and goes to X This denition of a random walk
generalizes the more familiar notion of a random walk on a Cayley graph of
a group, which is obtained by setting P to be a uniform distribution on the
elements of a generating set for G. A fundamental result of Markov [17] from
1906 (see also [1]) states that this random walk converges to the uniform
distribution on G, unless P is concentrated on a coset. A more recent
question of interest is to estimate the rate of convergence of the random walk
to its limit distribution. It is easy to see that this rate depends on the step
distribution P , and therefore all the results in this direction concentrate on
particular families of distributions for which good bounds can be obtained.
Here we ask a dierent question: Given a distance parameter - > 0, we ask
when do the distributions of X t and X t+c (for an appropriate constant c),
become -close to each other. Here we give a bound for the group Z q
(and
that does not depend on the step distribution P .
Theorem 3. Let P be a distribution on Z q
2 , and let X be the random walk
on Z q
2 with step distribution P . Let P t be the distribution of X at step
t. There is an absolute constant C, such that for every - > 0, if t
Finally, we consider the question of testing that a function f is identical
to a xed function h up to a permutation of its variables. Similar questions
were given consideration already in [19]. Here we construct a test for any
function h which is a k-junta that is given in advance.
Some notation about restrictions and permutations of vectors is needed
for the exact formulation of this result: Suppose that is
some subset of [n], whose elements are given in ascending order,
. For any permutation  : [k] ! [k] and every vector
f0; 1g n , we denote by xj (J) the vector
Theorem 4. Let be a function. The property, that
and some permutation
[k], is (; poly(; k))-testable for every .
1.2 Organization of the paper
We start with Section 2, where we give some preliminaries required for the
proofs, including a simple way to estimate the variation that a given coordinate
set I has on the input function f , and its connection with the Fourier
coe-cients of f . Section 3 uses it with a random partition of the coordinates
to provide our rst junta test; rst the 1-sided error non-adaptive version
is constructed, and then its variants are described. In Section 4 we present
our second junta test and its analysis.
We then provide the lower bound for non-adaptive junta testing in Section
5, deriving it from the result concerning random walks in Z q
2 that is
also proven there. In Section 6 we show how to test a function f for the
property of being identical to a permutation of a given function h.
We end the presentation with Section 7, which contains a discussion of
some possible directions for future research, and some open problems.
Preliminaries and testing for independence
To aid the presentation we use the following denition of functions which
are close to being a junta.
Denition 2 (a (k; )-junta). f is said to be a (k; )-junta if there exists
a Boolean k-junta g that agrees with f on at least a (1 )-fraction of the
points in its domain.
In terms of the above denition, an (; q)-test for the property of being
a k-junta uses q queries to distinguish between the case where the input
function is a k-junta, and the case where it is not a (k; )-junta.
Throughout the following we use the convention that Boolean functions
are of the as we shall rely in the sequel on
discrete harmonic analysis. An introduction to all that is required from
harmonic analysis for our paper is given in Appendix A, which also contains
some additional notation and facts from analysis.
We now turn to dene a measure of dependency of a boolean function f
on a given set of coordinates. The variation of f on a set I is proportional
to the probability that f does not yield the same values, for two random
locations that dier only on coordinates from I.
Denition 3 (variation). Let f : f0; 1g n !f1; 1g be a Boolean function,
and x a set I  [n] of coordinates. Let x 2 f0; 1g n be chosen uniformly at
random, and z 2 f0; 1g n be chosen by setting all the coordinates of z outside
I to be 0, and independently setting each coordinate i 2 I of z to be 0 with
probability 1=2 and 1 with probability 1=2. Then the variation of f on I is
dened by
The following lemma connects the variation of f on I with the Fourier
expansion of f .
Lemma 2.1. Let f : f0; 1g n ! f1; 1g be a Boolean function, and let
I  [n]. Then
Proof. Let x and z be randomly chosen as in Denition 3. Then
Since x and z are independent, for every S and T we have
The rst multiplicand above equals zero unless . The second multiplicand
equals zero unless T \ I = . We thus have
Since
we obtain that
as required.
The above lemma directly implies that the variation is monotone and sub-additive

2.2. Let f : f0; 1g n !f1; 1g be a Boolean function, and let I and
H be subsets of [n]. Then
Proof. Using Lemma 2.1. For example, to prove the left inequality we use
(S\I 6=)^(S\H 6=)
2.1 The independence test
Given a set I of coordinates, the independence test dened below is used
to determine whether a given Boolean function f is independent of the
coordinates in I. It is a simple two-query test as follows.
The Test. Choose a random x 2 f0; 1g n , and for every i 2 I, pick z i
randomly to either be 0 or 1. For every i 2 [n] n I, set z i to be 0. Verify
that
Properties of the Test. It is obvious that the independence test always
accepts if f is independent of the coordinates in I, and by Denition 3 its
rejection probability equals 1Vr f (I).
3 The size test
If f is a k junta, then it clearly has the following property: for every partition
I I r of the set of coordinates, there can be at most k subsets I j on
which f has non-zero variation. The size test veries this property in f . As
is proven later, this su-ces to verify that f is a k-junta.
The test. The test has two parameters, r and h, that are to be chosen
later. The test rst chooses a random partition I I r of the set [n] of
coordinates, by choosing for every coordinate i uniformly and independently
an index j 2 [r], and placing i in I j . It then identies on which of the I j 's f
has non-negligible variation, using 2rh queries, by going over every j from
1 to r and applying h iterations of the independence test to each I j (in
the next subsection we also provide an adaptive algorithm that achieves the
same in less queries). If f is found to be dependent on more than k subsets,
the test rejects, and otherwise it accepts.
Properties of the test. The size test obviously accepts every k-junta,
thus having perfect completeness. We show in the next subsection that,
for a proper setting of the parameters r and h, the size test accepts with
probability larger than 1=2 only if f is a (k; )-junta (since the test is 1-sided
this can easily be amplied to 1=3). Before we prove this, let us set the r
and h parameters.
The parameters of the test. Let us set r
Hence overall the test
makes queries to f .
3.1 Soundness of the Size-Test
Assume that f passes the test with probability 1=2. We prove that f must
be a (k; )-junta in two steps. We rst take J to be the set of coordinates on
which f has variation larger than some threshold t, and prove that jJ j  k.
Then we show that the total variation of f on coordinates outside J is
bounded by 2. This implies, by a simple argument, that f is -close to a
junta dominated by J .
2er
, and let J denote the set of all coordinates i for
which Vr f (fig) > t. We also denote
Proposition 3.1. If the size-test succeeds on f with probability 1=2, then
Proof. The key observation here is that if a set I of coordinates contains a
member of J , then the variation of f on that set is at least t (by Claim 2.2),
and therefore each iteration of the independence test on I detects the dependence
with probability at least t=2.
Assume on the contrary that jJ j > k. Since is easy to verify
that with probability at least 3=4 the number of subsets in the partition
I I r that contain an element from J is at least k + 1. When this
occurs, the probability that any of the rst
J will not be identied by the size test is bounded by (k
1))=t. Overall we have that
with probability at least 1=2 the size test rejects.
Having shown that jJ j  k, the proof of soundness will be complete by
showing that f is -close to a junta dominated by J . We actually show
that Vr f (
J) < 2. This is su-cient to complete the proof, according to the
following claim.
3.2. Let J be a set of coordinates satisfying Vr f (
J) < 2. Then there
exists a Boolean function h, that depends only on coordinates from J , and
agrees with f on at least a (1 )-fraction of the points in its domain.
Proof. Let z be a random element in f0; 1g n where the coordinates z i of z
J are each independently chosen to be 1 with probability 1=2 and 0
with probability 1=2, and the coordinates z i for are all set to 0. Now
h(x) equals the majority of the values of f over all inputs that agree with x
on the coordinates in J .
It is easy to verify that h depends only on the coordinates in J , so to
prove the claim, we show that f and h agree on at least a (1 )-fraction of
the inputs. Fix x 2 f0; 1g n , and let z be randomly chosen as above and y
be chosen independently from z, but with the same distribution. Denoting
Pr [f(xy) 6=
Note that for every x, p(x)  1=2. Therefore, if x is chosen uniformly
from f0; 1g n , we have
Pr x
x;z
Bounding Vr f (
It is left to show that Vr f (
J) < 2. Assume otherwise, and let us prove that
the test rejects with probability at least 1=2.
of the proof. The sum
never less than Vr f (
as follows from Claim 2.2. Since the sets I j are equidistributed, it follows
from the assumption that for any xed j,
J)=r  2=r.
We show that with high probability, the variation of f on more than k
of the sets in the partition is a substantial fraction of the lower bound
on its expectation. Sets with that much variation are detected with high
probability by the independence test, and so the size-test rejects f .
Denition 4. A set I j in the partition is said to be detectable if Vr f
er .
Lemma 3.3. Fix j, 1  j  r. The probability that I j is detectable, over
the choice of the partition I , is at least 3=4.
Before we prove Lemma 3.3, we show how it completes the proof. Let
denote the probability that the number of detectable subsets in the partition
is smaller than r=4. Since the number of detectable subsets is bounded by
Lemma 3.3 implies that4
number of detectable I j 's ]  3r
from which we have   1=3. Hence with probability at least 2=3, there
are at least subsets in the partition, whose variation
is larger than 2t. The size-test fails in this case with probability
at least 15=16, as follows from an argument similar to that in the proof of
Proposition 3.1. Therefore, the size-test rejects f with an overall probability
at least 1=2, as required.
It is only left to prove Lemma 3.3.
Proof of Lemma 3.3. We know that the expected variation on I j is larger
than =r, and we wish to bound its deviation. I j is a random subset, obtained
by going over the coordinates i 2 [n], taking each into I j with probability
1=r. We can view the random variable Vr f (I j ) as a sum of the gradual
donation of each coordinate,
In order to use standard deviation bounds for Vr f (I j ), we would like the
summands on the right-hand side to be independent, and bounded by a
small number, but neither of these hold (the i'th term in this sum is bounded
by Vr f (fig), but this could be large if i 2 J ). To correct this, we introduce
a technical tool that we call the unique-variation.
Denition 5 (unique-variation). For every subset S  [n], choose an
arbitrary coordinate i S 2 S, under the restriction that if S intersects
J then
the unique-variation of every subset I  [n] to be
It is easy to verify that for every I  [n], Ur f (I)  Vr f (I), and that
i2I Ur f (fig). One also notes that Ur f
J) > 2.
Dene, for every i 2 [n],
Then the Y i 's are independent random variables, each obtaining the value 1
with probability 1=r, and
hence a sum of independent non-negative random variables,
whose expectation is Ur f ([n])=r  2=r. Moreover, it follows from the definition
of J and of the unique-variation that each variable in this sum is
bounded by t. We can therefore apply standard deviation bounds to it, such
as the following Cherno-like bound, following Cherno-like bound, proven
in

Appendix

B.
be a sum of non-negative independent random
variables X i , and denote the expectation of X by . If each X i is bounded
above by t, then
et
for every  > 0.
ert
Hence the probability that I j is detectable is at least 3=4.
3.2 Improving the query complexity using adaptivity
The size test as described above applies several iterations of the independence
test to every subset in the partition, in order to detect whether it has
a non-negligible variation. Here we show how to detect all the subsets in
the partition that have non-negligible variation using less queries (reducing
one power of the dependency on k), by making the test adaptive.
Theorem 5. Set (as in the previous subsection). Then there exists
an adaptive one-sided k-junta test, that uses
queries.
Proof. The idea of the adaptive test is to speed up the nding of the subsets
in the partition with non-negligible variation as follows: Instead of applying
the independence test to each subset individually, we apply it to blocks, each
of which is a union of several such subsets. If f is not found to depend on a
block, then all of its elements can be declared to be 'variation free' at once.
When f is found to depend on a block, the algorithm divides the block into
two equally sized sub-blocks, for which the process is repeated.
Denition 6 (blocks). Fix a partition I I r of the coordinates. A set
B of coordinates is called a block, if it is the union of a positive number of
subsets in the partition. The size of the block is the number of subsets in the
partition that take part in this union.
The adaptive test. The adaptive test begin by randomly partitioning
the coordinates into subsets I . The test maintains, throughout its
operation, a set l g of at most k disjoint blocks with respect
to this partition. The blocks in S supposedly contain all the sets I j in the
partition that have non-negligible variation. Initially S is set to have only
one block which contains all coordinates, namely f[n]g. At each step,
the test performs the following.
If all the blocks in S are of size one, accept (in this case at most k
elements of the partition supposedly have non-negligible variation).
Otherwise, choose a block B 2 S that has the largest size. Remove B
from S, and partition it arbitrarily into two sub-blocks
whose sizes dier by at most 1.
Apply 4er ln(32k(1+log 2 r))
iterations of the independence test to B 0 . If f
is found to depend on B 0 , then insert B 0 into S, and otherwise discard
it. Apply the same treatment to B 00 .
If the size of S is now greater than k, reject (f depends on each of
the subsets in S, hence it is not a k-junta). Otherwise continue to the
next step.
The adaptive test obviously accepts with probability 1 if f is a k-junta.
To bound the number of rounds, we note that if after round T the maximum
size of the blocks is m, then clearly after round the maximum size of
the blocks is no more than d me. This implies that the algorithm terminates
after at most 2k(1+ log 2 r) steps, and that each step uses 16er ln(32k(1+log 2 r))
queries. The total number of queries made is therefore as required. To prove
Theorem 5, it is left to show that if f passes the test with probability at
least 1=2, then it is an (; k)-junta.
Proposition 3.5 (Soundness). If f passes the adaptive-test with probability
1=2, then it is an (; k)-junta.
Proof. Let
2er
and let J be dened as in the previous subsection ! . It !
su-ces to prove that jJ j  k and that Vr f (
J)  2. Assume on the contrary
that this is not the case, and let us prove that the adaptive-test rejects with
probability at least 1=2.
According to the proof of Proposition 3.1, if jJ j > k then with probability
at least 3=4 there are at least k subsets in the partition I whose
variation is at least t. Moreover, it is shown in the previous subsection
that if Vr f (
J) > 2, then with probability at least 2=3 there are at least
subsets in the partition, whose variation is at least =er = 2t. In both
cases, with probability at least 2=3 there are at least k subsets in the
partition whose variation is at least t.
To complete the proof we show that if there are at least k
with variation at least t in the partition I chosen by the adaptive
test, then the probability that it accepts is at most 1=8. This holds since in
order to accept, the test must at some point discard a block whose variation
is at least t. The probability of discarding each such block is at most
The test encounters two blocks at each step, so summing over all steps
bounds the probability that such a block is discarded throughout the test
by 1=8.
This concludes the proof of Theorem 5.
3.3 Improving the query complexity using two-sidedness
Instead of making the test adaptive, we can also reduce the number of queries
by giving up the perfect completeness requirement. That is, if the test is
allowed to reject a k-junta with probability at most 1=3 (and still rejects an
input that is not an (; k)-junta with probability at least 2=3), then we can
reduce a factor of k from the query complexity.
Theorem 6. Let ; - > 0 be any parameters, and x r
k)=. Then there exists a non-adaptive k-junta
test, which makes queries, and satises the following.
Every k-junta is accepted with probability at least 2=3.
Any input which is not an (; k)-junta is rejected with probability at
least 2=3.
As in the one-sided non-adaptive test, the two-sided test randomly partitions
the coordinates into r subsets. In order to reduce the number of
queries, the two-sided test nds the subsets in the partition that have non-negligible
variation by applying the independence test to blocks of such
subsets (see Denition 6), much like the adaptive test presented above ! . !
The two-sided test. First, the test randomly partitions the coordinates
into r subsets I I r . Then it picks s independent random sub-sets
each of size k. Each set  l determines a block
j2 l
I j , to which the test applies h iterations of the independence
test.
The test declares a set I j of the partition to be variation-free on account
of a block B l , if B l contains I j and f was not found to depend on B l . It
accepts f if all but at most k of the subsets of the partition are declared
variation-free on account of any of the blocks.
Properties of the test. It is obvious that the test performs 2sh queries,
as required. It is left to show that a k-junta is accepted by the test with
probability at least 2=3, and that an input which is not an (; k)-junta is
rejected with probability at least 2=3. This is proven in the next two propositions

Proposition 3.6 (completeness). If f is a k-junta, then it passes the
two-sided test with probability at least 2=3.
Proof. If f is a k-junta, then it is independent of all subsets in the partition
I except for at most k of them. To prove the proposition it is
therefore enough to show that every set I j which f does not depend on is
declared variation-free by the test with probability at least (1 1
3r ). For this
we show that if f is independent of I j then with probability at least (1 1
3r
over the choice of the blocks will be independent of at least
one of the blocks that contains I j .
We now x any partition I and suppose that f is independent
of I j . For any xed l, the probability over the selection of the blocks that f
is independent of B l is at least
14Conditioned on this event, the probability that B l also contains I j is at least
k=(r Hence with probability at least 1=20k, f does not depend
on B l and B l contains I j . The probability that this does not occur for any
B l is therefore bounded by
20k(2+ln r)
<3r
as required.
Proposition 3.7 (soundness). If f passes the two-sided test with probability
higher than 2=3, then it is an (; k)-junta.
Proof. Let
2er
and let J be dened as in Subsection 3.1 ! . It su-ces !
to prove that jJ j  k and that Vr f (
J)  2. Assume on the contrary that
this is not the case, and let us prove that the two-sided test rejects with
probability at least 2=3.
According to the proof of Proposition 3.1, if jJ j > k then with probability
at least 3=4 there are at least k detectable (see Denition 4) subsets in
the partition I I r . If Vr f (
J) > 2, then it follows from Lemma 3.3 that
the expectation of the number of detectable subsets, over the choice of the
partition I , is at least 3r=4. It follows, similarly to the discussion
following Lemma 3.3, that with probability at least 5=7, there are at least
detectable subsets in the partition.
Overall, the probability of having at least k detectable subsets is at
least 5=7 > 2=3 + 1=100. We conclude by showing that the probability of a
detectable set to be declared variation-free is bounded by 1
Let I j be a detectable subset of the partition, and let B l be a block that
contains it. By the monotonicity of the variation we have Vr f (B l ) > t, so
each iteration of the independence test on B l detects a dependency of f on
l with probability at least t=2. The overall probability of the test to not
nd dependency on B l , is therefore bounded by
I j is contained in at most s blocks, the probability of it being declared
variation-free is bounded by 1=100(k + 1), as required.
3.4 Further improvements and some remarks
Further improvements and generalizations of the tests in this section ! can !
be achieved, and will be presented in the full version of this paper. ! !!!
The two-sided test. It seems that the number of queries made by the
two-sided test can be improved to only have a quadratic dependency on k
(we omit logarithmic factors in this discussion). This can be achieved by
taking the 'junta threshold' t to be linear in 1=k instead of in 1=k 2 .
In this case if the set J is of size larger than k + 1, there will be, with
high probability, at least k+1 subsets in the partition with variation at least
linear in 1=k. Moreover, if Vr f (
J) > , then since the blocks to which the
independence test is applied are of size k, each of them will have variation
at least linear in 1=k with very high probability. This can be shown by
following the proof of Lemma 3.3 for blocks instead of for subsets in the
partition.
In both cases it is enough to make h, the number of iterations of the
independence test applied to each block, linear in k in order to detect all
these blocks.
Relaxing the soundness requirement. Note that the number of queries
made by the one-sided non-adaptive test may also be reduced to have
quadratic dependency on k, if the soundness requirement is somewhat relaxed
(as proposed to us by A. Wigderson). This is obtained if we only
require that the test accepts every k-junta, and rejects inputs which are,
say, not even (; 2k)-juntas.
To achieve the quadratic dependency on k, note that we chose the number
of elements in the partition to be quadratic in k, so that any k
in
uential coordinates would go into distinct subsets in the partition with
high probability. If we allow juntas of size 2k to be accepted, it is enough to
take a partition of size only linear in k. This reduces the number of queries
by a factor of k. But since the subsets in the partition are now larger, we
can take the 'junta threshold' to be linear in 1=k, and reduce by a factor
of k the number of independence tests applied to each subset, as explained
above for the two-sided case.
A purely combinatorial analysis. Note that the role of Fourier-Walsh
analysis in this section ! is limited { it is mostly used for the technical !
purpose of assigning a unique variation donation to each coordinate. In fact,
it seems that we can go through the analysis without using Fourier-Analysis
at all, as will hopefully be shown in the full version of this paper. This will
enable us to apply the tests described in this section in more generalized
settings. Specically, we hope to generalize the test to functions from [a] n
to [b], not only Boolean ones.
4 An alternative test
In this section we describe a two-sided ; O k 4
-test for the
property of being a k-junta. The approach of this test is somewhat more
algebraic, and this, combined with the fact that we do not insist on a 1-sided
error, allows for a more compact analysis.
An Overview of the testing algorithm. Let f be a k-junta. Let
(f) be the set of all elements are 0 on all the variables
that f depends on. Then V is clearly a subspace of f0; 1g n of co-dimension
at most k, and, moreover, it is an ideal under bitwise intersection, namely,
implies that x for every y. The crucial property of V is
that any x 2 V is an invariant shift for f : for any y 2 f0; 1g n we have
our test looks for a large ideal of invariant shifts
for f .
We will sample points in f0; 1g n and check whether they lie in V . Since
could be exponentially small, we sample according to a biased product
distribution  k on f0; 1g n , assigning to each bit 1 with probability 1
, and 0
with probability 1 1
k . It is easy to see that for any choice of a k-junta f
we have  k (V )  (1 1
1Given a point x chosen according to  k , we choose uniformly at random
a logarithmic number of points y 2 f0; 1g n . For each of these choices we
test that x ^ y is an invariant shift for f by choosing uniformly at random
a quadratic number of points z 2 f0; 1g n , and checking whether
Our testing algorithm will estimate the probability that a point x selected
according to  k behaves like an invariant shift, and accept f only if this
estimate is su-ciently large.
Testing Algorithm II for k-juntas
Let C be a a su-ciently large constant. Set
and
.
Choose m points x according to  k . For every selected x, choose
uniformly from f0; 1g n . For each choice of x and y
choose t 2 points z uniformly from f0; 1g n . All the choices are
independent.
For every selected point x check whether
every z and y that were selected for x. If this equality holds for
every z and y then we say that x passed the check .
If the fraction of points x that passed the check is at least
then return \ACCEPT". Otherwise return \RE-
JECT".
We rst observe that the query complexity of the algorithm is O(m  t 1
.
We next show that the test accepts every k-junta with probability at least
2=3.
Denition 7. For
For x 2 f0; 1g n , let p(x) denote the probability that x passes the check,
that is every z and y selected by the algorithm.
[p(x)] be the probability that a point x selected according
to  k passes the check.
Lemma 4.1. If f is a k-junta then the test returns \ACCEPT" with probability
at least 2=3.
Proof. Note that
k . Therefore p(f)  1 1
k  1. By Chebyshev's inequality, it
su-ces to take points x in order to ensure that the test returns
\ACCEPT" with high probability.
From this point on we focus on showing that if f is accepted with probability
greater than 1=3, then it is -close to being a k-junta.
Suppose that the test returns \ACCEPT" with probability greater than
1=3. Then by Chebyshev's inequality, p(f)  1 1
5k
. The next
denition will be useful in our analysis.
Denition 8. We call x good if Pr vx
> 1. Let G be
the set of all good x's.
It is not hard to choose the constant C (dened in the testing algorithm)
so that if x is not good, then p(x)  1+ 1
e
. Let 1 G () denote the
characteristic function of the set G. Then we have
[1 G (x)  p(x)]  p(f)10k
We now state our main claim, which, together with Claim 3.2, completes
the proof.
4.2. If  k (G)
, then there exists a set I, jIj  k,
such that Vr f (
In order to prove the claim we shall need a few lemmas.
Lemma 4.3.
Proof. Let it is easy to see that ^
f   v . Consequently

f   v
On the other hand,
R
Lemma 4.4. If x is good, then s(v)  1
Proof. Since by the denition of a good point x (Denition more than
half of the points v  x satisfy s(v)  1
can be
written as are two such points. Therefore
z
Pr
z
Lemma 4.5. If x is good, then
Proof. By combining Lemmas 4.4 and 4.3 we get that for all possible u  x it
holds that
. Averaging this inequality
over all u  x, and observing that for R\x 6= ;, exactly half of the possible
Proof of Claim 4.2: Averaging the inequality of Lemma 4.5 over all x in G,
according to  k we obtain
R
G; R \ x 6= ;)
Now consider singletons R. We claim that at most k singletons
may satisfy  k (x2G;i2x)
Indeed, if it were otherwise, let B be a
family of k singletons. Let A i be the set fx 2 G; x
Bg. Therefore
and we reach a contradiction. Let I be the family of all singletons fig for
which  k (x2G;x i =1)
We have shown jIj  k. Now, for any R 6 I,
R\
I 6=
5 Lower bounds and a random walk on Z qWe use Yao's principle, which says that to show a lower bound on the
complexity of a randomized test, it is enough to present an input distribution
for which any deterministic test with that complexity is likely to fail.
We dene distributions D P ; DN on positive (k-junta) and negative ( 1-far
from any k-junta) inputs, respectively. Our input distribution rst chooses
D P or DN with equal probability and then draws an input according to the
chosen distribution. We show that every deterministic non-adaptive test
with
O(
queries has error probability larger than 1=3 (with respect
to the induced probability on inputs). For this purpose we show that for
any set of
O(
vertices of the hypercube, the distributions D P and
DN induced on f1; 1g q by restricting the functions to these q vertices have
a variation distance less than 1The distributions D P and DN are simply uniform distributions over
characters  S of size k and k respectively. We will, however, work with
two auxiliary distributions ~
DN , which are close to D P and DN , and
which are easier to analyze. To choose a function from ~
D P , we choose a
random set S  [n], jSj  k, by picking k random elements in [n] with
repetition, and take the character  S . The distribution ~
DN is dened in the
same manner, but that we choose k
Note that if jSj > k, then the character  S is 1-far from any k-junta;
and that both kD P
~
DN k are bounded by O
Now, consider the distributions induced by ~
DN on f1; 1g q . Let
be the queries, and let M be a q  n boolean matrix, with rows
To choose an element x of f1; 1g q according to the rst distri-
bution, we choose at random, allowing repetitions, k columns of M and sum
them up. This gives us an element y of f0; 1g q . We take
the power operation is performed coordinate-wise. The same holds for the
second distribution, the only dierence being that we choose k
For
be the probability of choosing x when we pick a
column of M at random. Consider a random walk on Z starting
at 0, in which at every step we choose an element of the cube according to P
and add it to the current location. Let P t be the distribution induced by this
walk after t steps. Note that P k , P k+2 are precisely the distributions induced
by ~
DN . Note also that P t is the distribution of Y Y
we sum t independent copies of a Z q-valued random variable Y , taking every
value x with probability P (x).
We want to show that for t su-ciently large compared to q, the distributions
are close in the variation distance. This is Theorem 3,
presented in the introduction. Theorem 2 (see the introduction) now follows
as an immediate corollary.
Theorem 3 is proven below. We rst give a a very brief overview of the
proof. Every element x of Z qdenes a partition of the space into a subspace
its complement V 1 . x is said to be a degenerate
direction if the probability of either of these sets is at most ~
O
. The
proof is inductive on the dimension q. We distinguish between two cases: if
there are no degenerate directions, then the random walk is exponentially
close to being stationary after ~
O
steps, and the claim holds. If, on the
other hand, there is a degenerate direction x, then the walk 'splits' into two
'independent' walks, one on V 0 and one on V 1 , each of which is isomorphic
to Z q 1
2 , and we can use induction.
5.1 Proof of Theorem 3
Let us consider the distribution P t of the walk at time t. Recall that the
distribution of the sum of two independent random variables is the convolution
(see Appendix A) of their distributions, (P
This implies that P t is the t-wise convolution of P , which we will denote by
Now, for any r  t we have kP t P t+2
k. The following fact is well-known
and easy: for any two functions f; g on Z qit holds that kf  gk 1
Taking into account that P (t r) is a distribution we deduce
Therefore, the distance kP t P t+2 k is monotone non-increasing in t, and we
are interested in the rst time are -close.
We show t(q)  O
log 1
, where we set b(q)
This is an immediate consequence of the following proposition, where S
is the sum of the convergent series
Proposition 5.1. There exists an absolute constant C such that for any
q  1, for any distribution P on Z q
2 , and for any t  C log 1
Proof. The proof is by induction on q.
We will assume, where needed, that C is su-ciently large. We set
assuming this is an integer.
The case is easy. It is possible to show that for a distribution P on
. A simple analysis shows that if t  C log 1
- , the last expression
is at most -
Assume the claim for holds for q 1.
We proceed with simple Fourier analysis, and show that our claim is true
if all the non-zero Fourier coe-cients of P are relatively small (a nice way
to see this, though the actual proof is even simpler, is that this condition
on the Fourier coe-cients implies that P t converges rapidly to the uniform
distribution U , and kP t P t+2 k  kP t Uk We have
R
R
a t (R) a t+2 (R)
(R).
x
Now consider the case in which, for all R 6=  we have ja(R)j  1 -q
In this case, the right hand side of (1) is at most
a 2t (R)  2 q
2C
log 1
This is smaller than -
.
It remains to deal with the case where P has large Fourier coe-cients.
Let R be such that ja(R)j  1 -q
We make two assumptions for the sake of clarity: we assume that
and that a(R)  0. Both assumptions are easily shown not
to lead to loss of generality and we omit the proofs.
1g. It follows that
Observe that the direction e 1 is degenerate, it partitions the cube f0; 1g q
into two subcubes both of which
are isomorphic to Z q 1. Because of the degeneracy of e 1 , the walk will nd
it hard to leave the subcube it is in, and we will 'split' it into two walks, on
use the induction hypothesis for these walks.
For
r
distributions
so obtained can be viewed as distributions on Z q 1
.
We write P t as a convex combination P
do the same for P t+2 . Note that
-q
. We will show,
using the induction hypothesis, that for
This will conclude the proof, since
r be a random variable counting
the number of times the walk makes a step in direction x with x during
the rst r steps.
The other case is treated similarly.
The central (though simple) point of the argument is that for any r and
for any even ' we have
This is true because the distribution on the left hand side is the distribution
on Z q 1
given that the walk makes ' 'odd' steps x with x
'even' steps, with x the addition in Z q
2 is commutative, we might
as well assume that all the odd steps were made rst, giving the right hand
side.
Therefore,
r can be written as a convex combination
'r;' even
Using this, we can bound kP 0
q
q;' even
k: (2)
The rst summand in (2) is equal to the probability that an odd step was
made in one of the times t 2, and this is at most -q
As to the second summand, observe that N t is a binomial random variable
with parameters
. The probability of
the second summand is that of N t
-  q, and this, using Cherno
bounds, is at most exp
Thus, the sum of the two rst summands is bounded from above by
It remains to deal with the third summand. For '
-  q we
have
-  b(q 1), and therefore we
may use the induction hypothesis to conclude
Consequently, the third summand in (2) is bounded from above by
concluding the proof of the proposition and of Theorem 3.
6 Testing that f is a permutation of a given h
Given a Boolean function h : f0; 1g n ! f1; 1g, we say that a function f
is a permutation of h if there exists a permutation  : [n] ! [n], such that
for every
(with a slight abuse of notation) We show a test
for this property for any h that is a k-junta. We rst show a test with a
linear dependence in  1 but an exponential one in k, and then show how to
change it to a test with a polynomial dependence on  1 and k. On the other
hand, a closer look at the proof of Theorem 2 shows that it also provides a
lower bound on testing that f is a permutation of
which is a function of k, so the limitation that h has a small junta is essential.
The tests constructed in the following are 2-sided. This is not a coin-
cidence, as the following proposition shows that in some cases one needs a
number of queries that depends on n to provide a 1-sided test for being a
permutation of a given h. On the other hand, [15] in particular provides
such a 1-sided test making a number of queries that is logarithmic in n.
Proposition 6.1. A non-adaptive testing algorithm that makes less than
log(n=2) queries on f(x), and accepts any permutation of
with probability 1, will necessarily accept some permutation of h 0
with probability at least 1
.
Proof. Suppose that we are given a sequence of l = log(n=2) queries, labeled
by q
dene an equivalence
relation over ng by stating that i  i 0 if for every 1  j  l we have
. We say that i is isolated if its equivalence class is fig.
We observe that by the choice of l for every set of l queries there exist
a set of at least ncoordinates that are not isolated. Thus, for every non-adaptive
testing algorithm there exists a coordinate i with the property that
it is not isolated with probability at least 1
.
Now, for every query sequence q (l) for which i is not isolated,
and which is taken with positive probability by the algorithm, let i 0 be
such that i  i 0 . Since the algorithm has to accept
probability 1, the algorithm must accept this function when the sequence
chosen. But this means that the algorithm must accept also
the function f 0 sequence is chosen, because these two
functions are identical on that whole query sequence. Summing up over all
query sequences for which i is not isolated, we conclude that the algorithm
must accept f 0 with probability at least 1, completing the proof.
We now turn to the proof of Theorem 4. The constructed tests are adap-
tive, but they could be made non-adaptive with a penalty of an additional
poly(k) factor. On a related issue, Appendix C contains an application of
Theorem 1 to the question discussed in [19] about testing that a function is
a k-monomial.
6.1 A test with an exponential dependency on k
We assume without loss of generality that g depends on all its variables. In
this case, the variation of g on every coordinate is at least 2 1 k . We begin by
performing the k-junta test given by Theorem 1 on f , with minf as
the approximation parameter and 7as the detection probability (we use the
usual amplication techniques). If the test rejects then we reject the input.
If it accepts, we note that with high probability we have sets U
of
coordinates such that each of them contains exactly one member of a junta
J of a function f 0 that is close to f (with l  k). If l < k we reject the
input, so from now on let us assume that l = k, and for convenience denote
We rst show how to test for the above property in the special case that
g is symmetric with regards to permutations of its variables, and then show
how to generalize it to every g.
We check f(x) at a randomly chosen x 2 f0; 1g n for equality with g(xj J ),
and repeat this times so that any f(x) that is 1-far from g(xj J )
will be rejected with probability at least 7. However, since we do not know
we perform the following.
Let us for the randomly chosen x denote by Z x the set of its zero co-ordinates
0g. We construct y 2 f0; 1g k as follows. For every j, we
perform 3  2 k (log h iterations of the independence test for
to know with high probability whether Vr f (Z x \
do the same for V j nZ x (remember that in a k-junta, every set containing a
junta coordinate has variation at least 2 1 k ). The probability that in any
of the h iterations such a dependence will not be detected is bounded by 1If only V j \ Z x is found to have variation then we set y
this means that the junta coordinate in V j has the value 0. By the same
token, if only V j nZ x is found to have variation then we set y
any of the other two cases (for the same j) we reject the input. Having
constructed y, we compare f(x) with g(y). The construction of y according
to the variation tests above ensures that with high probability xj y, and
thus we are done.
For an asymmetric g we use a similar test as above, performing
iterations of the comparison above, to ensure that for
every permutation  is -far from g(xj (J) ) then this is
detected with probability at least 1 1=8k!. We use the same queries for
every of the k! (or less) possible permutations of g, and so with probability8
we will detect -farness from any such permutation for which it exists.
The algorithm accepts the input if there was any permutation of g for which
this was not detected. Summing up, an input which is -far from being any
permutation of g will be rejected with probability at least 5, and an input
which was a permutation of g will be accepted with probability at least 6(it could only be rejected if the k-junta test did not detect all the junta
coordinates, or if in some stage the dependence of f on Z x \V j or on V j nZ x
is not correctly detected).
6.2 Reducing the dependency on k
We construct here a test for f being a permutation of g using O( 3 (log k
queries. The running time itself is still exponential in k, however

First, we perform the k-junta test with the approximation parameter
We denote U
as before. However, after the size test we again use
the independence test to distinguish between Vr f (U i j
and Vr f (U i j
for every j, and discard from U
also the sets whose variation is
low. Let us denote the undiscarded sets by . Here we allow also for
the possibility that m < k, as it could be the case that some sets containing
junta coordinates were not detected by the size test or were discarded in the
next phase.
Given any function ~
on m coordinates, that has the additional property
that every coordinate has variation at least
4k with respect to it, we perform
the following procedure. We choose a uniformly random x 2 f0; 1g n , and
denote Z x as before. For every j we use 12 1 k log(hk) iterations of the
independence test to check with probability at least 1 1
or V j nZ x have variation at least
(if both or none of the two sets has it we
reject the input). We then construct y as above and check that
We perform iterations of the above; we
distinguish with probability between the case that the probability
of
g(y) is at least 1 1, and the case that it is at most 1 1
(see [2,

Appendix

A] for the large deviation inequality used here).
In order to accommodate g, we consider every ~ g which is a restriction
of any permutation of g to any subset of its coordinates that includes all
those that have variation at least
, and may include any coordinates with
variation at least
as well. With probability at least 5the above will give
the correct answer for all the possible ~
we accept the input if at least one
of them has the higher probability for
g(y).
7 Some open problems
It would be interesting to tighten the bounds on the number of queries
required to test for the property of being a k-junta, especially with regards to
the power of k appearing in these expressions. Trying to nd an
bound for some  > 1 is a particularly appealing option. We conjecture that
is the appropriate lower bound, even if we also allow for the relaxed
notion of a test that has to reject only inputs which are not (; 2k)-juntas.
There are also interesting questions related to hardness of approxima-
tions. In particular, it would be interesting to see what is the best error
probability (with regards to ) that can be achieved from tests that query
f in a constant number of points that is independent of . It would also
be interesting to construct consistent readers for juntas, in the spirit of the
consistent readers for low degree polynomials used for constructing Probabilistically
Checkable Proofs ([3, 4], see also [8]).
Another open problem goes back to the primal question of characterizing
the testable properties: Can one formulate conditions relating to the Fourier
transform of functions, such that all properties of functions that satisfy them
are testable?
There is also an open problem arising from the proof of the lower bound:
For what groups G (other than Z q
2 ) can one prove a convergence result
similar to Theorem 3?
Finally, with regards to testing that f is a permutation of a given function
h, we can pose the following question: If we know that a function h with n
variables is far from all k-juntas, does it imply a lower bound (that depends
on on the number of queries required for testing that f is a permutation of
h? The lower bound proof on k-junta testing already implies such a bound
for some functions h, namely, those that are characters of size k.



--R


The Probabilistic Method
Proof veri
Probabilistic checking of proofs: A new characterization of NP
Learning in the presence of

Worst Case vs. Average Case
PCP: Approaching a Polynomially-Small Error-Probability
Improved testing algorithms for monotonicity
The art of uninformed decisions: A primer to property test- ing
Monotonicity testing over general poset domains
Boolean functions with low average sensitivity depend on few coordinates

Property testing and its connections to learning and approximation
Finding relevant variables in PAC model with membership queries
Learning quickly when irrelevant attribute abound: A new linear-threshold algorithm
Extension of the law of large numbers to dependent events
Learning functions of k hidden variables
Proclaiming dictators and juntas or testing Boolean formulae

Robust characterization of polynomials with applications to program testing
Optimal attribute-e-cient learning of disjunctions


--TR
Learning in the presence of finitely or infinitely many irrelevant attributes
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
Probabilistic checking of proofs
Proof verification and the hardness of approximation problems
Property testing and its connection to learning and approximation
PCP characterizations of NP
The importance of being biased
Monotonicity testing over general poset domains
Robust Characterizations of Polynomials withApplications to Program Testing
Testing Basic Boolean Formulae
Learning Quickly When Irrelevant Attributes Abound
Optimal Attribute-Efficient Learning of Disjunction, Parity and Threshold Functions
Finding Relevant Variables in PAC Model with Membership Queries
Learning juntas
discrete Fourier analysis;property testing;juntas;boolean functions