arXiv:1611.07879v1 [] 23 Nov 2016

Testing submodularity and other properties of valuation functions
Abhinav Bommireddi
School of Computer Science
University of Waterloo
vabommir@uwaterloo.ca

Eric Blais
School of Computer Science
University of Waterloo
eric.blais@uwaterloo.ca

November 24, 2016

Abstract
We show that for any constant ǫ > 0 and p ≥ 1, it is possible to distinguish functions
f : {0, 1}n → [0, 1] that are submodular from those that are ǫ-far from every submodular
function in ℓp distance with a constant number of queries.
More generally, we extend the testing-by-implicit-learning framework of Diakonikolas et
al. (2007) to show that every property of real-valued functions that is well-approximated in
ℓ2 distance by a class of k-juntas for some k = O(1) can be tested in the ℓp -testing model
with a constant number of queries. This result, combined with a recent junta theorem of Feldman and Vondrák (2016), yields the constant-query testability of submodularity. It also yields
constant-query testing algorithms for a variety of other natural properties of valuation functions, including fractionally additive (XOS) functions, OXS functions, unit demand functions,
coverage functions, and self-bounding functions.

1

Introduction

Property testing is concerned with approximate decision problems of the following form: given
oracle access to some function f : X → Y and some fixed property P of such functions, how many
oracle calls (or queries) to f does a bounded-error randomized algorithm need to distinguish the
cases where f has the property P from the case where f is ǫ-far—under some appropriately defined
metric—from having the same property? Remarkably, many natural properties of functions can
be tested with a number of queries that is independent of the size of the function’s domain. For
example, for any constant ǫ > 0 and t ≥ 1, a constant number of queries suffices to test whether
a Boolean function f : {0, 1}n → {0, 1} is linear [7]; a polynomial of degree at most t [27]; a
t-junta [5, 18]; a monomial [26]; computable by a Boolean circuit of size t [10]; or a linear threshold
function [24].
In this work, we consider the problem of testing properties of bounded real-valued functions over
the Boolean hypercube. In particular, are there natural examples of such properties that are testable
with a constant number of queries? This question is best considered in the ℓp testing framework
introduced by Berman, Raskhodnikova, and Yaroslavtsev [4]. In this setting, the distance between a
function f : {0, 1}n → [0, 1] and some property P of these functions is distp (f, P) = inf g∈P kf − gkp .

1

1.1

Testing properties of valuation functions

Natural properties of bounded real-valued Boolean functions have been studied extensively in the
context of valuation functions in algorithmic game theory. For a sequence of n goods labeled with
the indices 1, . . . , n, we can encode the value of each subset of these goods to some agent with a
function f : {0, 1}n → [0, 1] by setting f (x) to be the (possibly normalized) value of the subset
{i ∈ [n] : xi = 1} to the agent. Such a valuation function f is
P
Additive if there are weights w1 , . . . , wn such that f (x) = i:xi =1 wi ;
a Coverage function if there exists P
a universe U , non-negative weights {wu }u∈U , and subsets
A1 , ..., An ⊆ U such that f (x) = u∈S
Ai wu .
i:xi =1

Unit demand if there are weights w1 , . . . , wn such that f (x) = max{wi : xi = 1};

OXS if there are k ≥ 1 unit demand functions g1 , . . . , gk such that f (x) = max{g1 (x(1) ), . . . , gk (x(k) )}
P
(j)
where the maximum is taken over all x(1) , . . . , x(k) such that for every i ∈ [n], xi = kj=1 x i ;
P
Gross Substitutes
if for any p′ ≤ p ∈ Rn and any x, x′ that maximize f (x) − i:xi =1 pi and
P
f (x′ ) − i:x′ =1 p′i , respectively, every j ∈ [n] for which xj = 1 and pj = p′j also satisfies
i
x′j = 1;
Submodular if f (x) + f (y) ≥ f (x ∧ y) + f (x ∨ y) for every x, y ∈ {0, 1}n , where ∧ and ∨ are the
bitwise AND and OR operations;
Fractionally subadditive
P (XOS) iff there are non-negative real valued weights {wij }i,j≤n such
that f (x) = maxi j wij · xj ;
P
Self-bounding if f (x) ≥ i (f (x) − minxi f (x)), where minxi f (x) = min{f (x), f (x ⊕ ei )} and ⊕
is the bitwise XOR operator; and
Subadditive if f (x ∪ y) ≤ f (x) + f (y) for every x, y ∈ {0, 1}n .
Each of these properties enforces some structure on valuation functions, and much work has been
devoted to better understanding these structures (and their algorithmic implications) by studying
the properties through the lenses of learning theory [2, 3, 15], optimization [13, 14], approximation [16, 17], and sketching [1]. The problem of testing whether an unknown valuation function
satisfies one of these properties offers another angle from which we can learn more about the
structure imposed on the functions that satisfy these properties.
Indeed, there has already been some recent developments on the study of testing these properties. Notably, Seshadhri and Vondrák [29] initiated the study of testing submodularity for functions
over the hypercube and showed that in the setting where we measure the distance to submodularity
in terms of Hamming distance (rather than ℓp distance), submodularity can be tested with
√
n
log
n queries and that it cannot be tested with a number of queries that is independent of n.
−
ǫ
Subsequently, Feldman and Vondrák [17] showed that in the ℓ1 testing framework, we can do much
better: testing submodularity in this model requires a number of queries that is only logarithmic
in n. Our first result shows that, in fact, for any value of p ≥ 1, it is possible to test submodularity
in the ℓp setting with a number of queries that is completely independent of n.

2

Theorem 1.1. For any ǫ > 0 and any p ≥ 1, there is an ǫ-tester for submodularity in the ℓp testing
max{2,p} )
.
model with query complexity 2Õ(1/ǫ
Another property that has been considered in the (standard Hamming distance) testing model
is that of being a coverage function. Chakrabarty and Huang [8] showed that for constant values of
ǫ > 0, O(nm) queries suffice to ǫ-test whether a function f is a coverage function on some universe
U of size |U | ≤ m. Note that, unlike in the learning and approximation settings, bounds on the
number of queries required to test some property P do not imply anything about number of queries
required to test properties P ′ ⊂ P, so even though coverage functions are submodular, results
on testing submodularity do not imply any bounds on the query complexity for testing coverage
functions. Nonetheless, our next result shows that this property—along with most of the other
properties of valuation functions listed above—can also be tested with a number of queries that is
independent of n.
Theorem 1.2. For any ǫ > 0 and any p ≥ 1, there are ǫ-testers in the ℓp testing model for
• additive functions, coverage functions, unit demand functions, OXS functions, and gross submax{2,p} )
stitute functions that each have query complexity 2Õ(1/ǫ
; and
Õ(1/ǫmax{2,p} )

• fractional subadditivity and self-bounded functions that have query complexity 22

.

Theorems 1.1 and 1.2 are both special cases of a general testing result that we obtain by
extending the technique of testing by implicit learning of Diakonikolas et al. [10]. We describe this
general result in more details below.

1.2

Testing real-valued functions by implicit learning

There is a strong connection between property testing and learning theory that goes back to the
seminal work of Goldreich, Goldwasser, and Ron [21]. As they first observed, any proper learning
algorithm for the class of functions that have some property P can also be used to test P: run the
learning algorithm, and verify whether the resulting hypothesis function h is close to the tested
function f or not. This approach yields good bounds on the number of queries required to test
many properties of functions, but, as simple information theory arguments show, it cannot yield
query complexity bounds that are smaller than log n for almost all natural properties of functions
over {0, 1}n .
Diakonikolas et al. [10] bypassed this limitation for the special case when every function that
has some property P is close to a junta. A function f : {0, 1}n → [0, 1] is a k-junta if there
is a set J ⊆ [n] of cardinality |J| ≤ k such that the value of f on any input x is completely
determined by the values xi for each i ∈ J. Every k-junta f has corresponding “core” functions
fcore : {0, 1}k → {0, 1} that define its value based on the value of the k relevant coordinates of
its input. Diakonikolas et al.’s key insight is that for testing properties whose functions are (very)
close to juntas, it suffices to learn the core of the input function—without having to identify the
identity of the relevant coordinates.
The wide applicability of the testing-by-implicit-learning methodology is due to the fact that
for many natural properties of Boolean functions, the functions that have these properties must
necessarily be close to juntas under the Hamming distance. The starting point for the current
research is a recent breakthrough of Feldman and Vondrák, who showed that a similar junta theorem
3

holds for many properties of real-valued functions when closeness is measured according to ℓ2
distance.
Feldman–Vondrák junta theorem. Fix any ǫ ∈ (0, 12 ). For every f : {0, 1}n → [0, 1],
• if f is submodular then there exists a submodular function g : {0, 1}n → [0, 1] that is a
O( ǫ12 log 1ǫ )-junta such that kf − gk2 ≤ ǫ; and
• if f is self-bounding then there exists a self-bounding function g : {0, 1}n → [0, 1] that is a
1
2O( ǫ2 ) -junta such that kf − gk2 ≤ ǫ;
The logarithmic dependence on n for the problem of testing submodularity in the ℓ1 testing
model [17] follows directly from Feldman and Vondrák’s junta theorem and the (standard) testingby-proper-learning connection. This junta theorem also suggests a natural approach for obtaining
a constant query complexity for the same problem by combining it with a testing-by-implicitlearning algorithm. In order to implement this approach, however, new testing-by-implicit-learning
techniques are required to overcome two obstacles.
The first obstacle is that all existing testing-by-implicit-learning algorithms [9–11, 22] are designed for properties that contain functions which are close to juntas in Hamming distance, not ℓp
distance. This is a stronger condition, and enables the analysis of these algorithms to assume that
with large probability, when f is very close to a k-junta f ′ , the queries x made by the algorithm all
satisfy f (x) = f ′ (x). In the ℓp distance model, however, we can have a function f that is extremely
close to a k-junta but still has f (x) 6= f ′ (x) for many (or even every!) input x.
The second (related) obstacle that we encounter when considering submodular functions is that
current testing-by-implicit-learning algorithms only work in the regime where the functions in P
are ǫ-close to k-juntas for some k < ǫ−1/2 . (See for example the discussion in §2.5 of [28].) This
condition is satisfied by the properties of Boolean functions that have been studied previously, but
the bounds in the Feldman–Vondrák junta theorem, however, do not satisfy this requirement.
We give a new algorithm for testing-by-implicit-learning that overcomes both of these obstacles.
As a result, we obtain the following general theorem.
Theorem 1.3. For any 0 < ǫ < 12 and any property P of functions mapping {0, 1}n → [0, 1], if
k ≥ 1 is such that for every function f ∈ P, there is a k-junta h that satisfies kf − hk2 ≤ 10ǫ6 , then
there is an ǫ-tester for P in the ℓ2 testing model with query complexity

2O(k log k)
.
ǫ10

Theorems 1.1 and 1.2 are both obtained directly from Theorem 1.3, the Feldman–Vondrák junta
theorem and Fact 2.1.

1.3

Overview of the proofs

The algorithm. The current testing-by-implicit-learning algorithms proceed in two main stages.
In the first stage, the coordinates in [n] are randomly partitioned into poly(k) parts, and an influence
test is used to identify the (at most k) parts that contain relevant variables of an unknown input
function f that is very close to being a k-junta. In the second stage, inputs x ∈ [n] are drawn at
random according to some distribution, the value f (x) is observed, and the value of the relevant
coordinate in each of the parts identified in the second stage is determined using more calls to the
influence test.

4

The Implicit Learning Tester algorithm that we introduce in this paper reverses the order
of the two main stages. In the first stage, it draws a sequence of q queries X = (x(1) , . . . , x(q) )
at random and queries the value of f on each of these queries. It also uses X to partition the
coordinates in [n] into 2q random parts according to the values of the coordinate on the q queries.
In the second stage, the algorithm then uses an influence estimator to identify the k parts that
contain the relevant coordinates of a k-junta that is close to f and, since all the coordinates in
a common part have the same value on each of the q queries, learn the value of the k relevant
coordinates on each of these initial queries. The algorithm then checks whether the core function
thus learned is consistent with those of functions in the property being tested.
The main advantage of the Implicit Learning Tester algorithm that its analysis does not
require the assumption that our samples are exactly consistent with those of an actual k-junta
(instead of those of a function that is only promised to be close to a k-junta). This feature enables
us to overcome the obstacles listed in the previous section, at the cost of adding a few complications
to the analysis, as described below.
The analysis. There are two main technical ingredients in the analysis of the algorithm. The
first, established in Lemma 3.1, is used to show that when f is close to a k-junta in ℓ2 distance,
the search procedure identifies parts that contain the k relevant coordinates of some k-junta that
is close to f . (Note that the search is not guaranteed to find the parts that contain the relevant
coordinates of the k-junta that is closest to f , but it suffices to find those of any close k-junta.)
The second technical ingredient addresses the fact that by drawing the q samples x(1) , . . . , x(q)
first and then using these samples to provide the initial partition of the coordinates in [n], we no
longer will obtain uniformly random samples of the core fcore of the input function f . Nonetheless,
in Lemma 3.2, we show that when f is close to a k-junta, the distribution of these samples on the
core function still enables us to accurately estimate the distance of fcore to the core functions of
any other k-junta.

1.4

Discussion and open problems

Theorems 1.1–1.3 raise a number of intriguing questions. The most obvious question left open is
whether we can also test subadditivity of real-valued functions with a constant number of queries:
subadditive functions need not be close to juntas, so such a result would appear to require a different
technique.
It is also useful to compare our bounds for submodularity testing with those for testing monotonicity: in the Hamming distance testing model, Seshadhri and Vondrák [29] showed that the
query complexity for testing submodularity is at least as large as that for testing monotonicity.
However, the best current bounds for testing monotonicity in the ℓp testing model have a linear
dependence on n [4]. Is it also possible to test monotonicity with a constant number of queries?
Or is it the case that testing submodularity is strictly easier than testing monotonicity in the ℓp
testing setting?

2

Preliminaries

Let Fn denote the set of functions mapping {0, 1}n to [0, 1]. For any f ∈ Fn and S ⊆ [n] with
complement S = [n] \ S, when x ∈ {0, 1}S and y ∈ {0, 1}S , we write f (x, y) to denote the value
5

f (z) for the input z that satisfies zi = xi for each i ∈ S and zi = yi otherwise.
We use the standard definitions and notation for the Fourier analysis of functions f : {0, 1}n →
[0, 1]. For a complete introduction to the topic, see [25]. Throughout the paper, unless otherwise specified all probabilities and expectations are over the uniform distribution on the random
variable’s domain.

2.1

Property testing

A property P of functions in Fn is a subset of these functions that is invariant under relabeling of
the n coordinates. The Hamming distance between f, g ∈ Fn is distHam (f, g) = Prx [f (x) 6= g(x)]
and the Hamming distance between f and a property P is distHam (f, P) = inf g∈P distHam (f, g).
For p ≥ 1, the ℓp distance between f and g is distp (f, g) = kf − gkp = (Ex [|f (x) − g(x)|p ])1/p and
the ℓp distance between f and P is distp (f, P) = inf g∈P distp (f, g).
Given ǫ > 0, An ǫ-tester in the Hamming testing model (resp., ℓp testing model) for some
property P ⊆ Fn is a randomized algorithm that (i) accepts every function f ∈ P with probability
at least 32 and (ii) rejects every function f that satisfies distHam (f, P) ≥ ǫ (resp., distp (f, P) ≥ ǫ)
with probability at least 23 . An ǫ-tester for P is an (ǫ′ , ǫ)-tolerant tester, for some ǫ′ < ǫ if it
additionally accepts every function f that satisfies distHam (f, P) ≤ ǫ′ (resp., distp (f, P) ≤ ǫ) with
probability at least 32 .
Our proofs of Theorems 1.1–1.3 are established in the ℓ2 testing model. The result for general
ℓp testing models is obtained from the following elementary relation between the query complexities
of testing any property in different ℓp testing models.
Fact 2.1 (c.f. Fact 5.2 in [4]). For any P ⊆ Fn , any ǫ > 0, and any p ≥ 1, the number Qp (P, ǫ) of
p
queries required to ǫ-test P in the ℓp testing model satisfies Q2 (P, ǫ) ≤ Qp (P, ǫ) ≤ Q2 (P, ǫ 2 ).
Theorem 1.2 also relies on the following hierarchy of properties. (See, e.g., [23].)
Lemma 2.2. The properties of Fn defined in the introduction satisfy the inclusion hierarchy
Additive ⊆ Coverage ⊆ Unit demand ⊆ OXS ⊆ Gross substitute ⊆ Submodularity ⊆ XOS ⊆ Self-bounding.

2.2

Juntas

The function f : {0, 1}n → [0, 1] is a junta on the set J ⊆ [n] if for every x, y ∈ {0, 1}n that
satisfy xi = yi for every i ∈ J, we have f (x) = f (y). The function f is a k-junta if it is a
junta on some set J ⊆ [n] of cardinality |J| ≤ k. The function fcore : {0, 1}k → [0, 1] is a core
function of the k-junta f : {0, 1}n → [0, 1] if there is a projection ψ : {0, 1}n → {0, 1}k defined
by setting ψ(x) = (xi1 , . . . , xik ) for some distinct i1 , . . . , ik ∈ [n] such that for every x ∈ {0, 1}n ,
f (x) = fcore ψ(x) .
Definition 2.3. For any function f : {0, 1}n → [0, 1] and set J ⊆ [n], the J-junta projection of f is
the function fJ : {0, 1}J → [0, 1] defined by setting fJ (x) = Ey∈{0,1}J [f (x, y)] for every x ∈ {0, 1}J .
A basic fact that we will require is that fJ is the J-junta that is closest to f under the ℓ2 metric.
Proposition 2.4. For every f : {0, 1}n → [0, 1] and J ⊆ [n], if g : {0, 1}n → [0, 1] is a J-junta,
then dist2 (f, fJ ) ≤ dist2 (f, g).
6

Proof. By applying the identity kf − gk22 = kf − fJ + fJ − gk22 and by expanding the right-hand
side, we obtain
#
"
h
i

2
f (x, y) − fJ (x, y) + fJ (x, y) − g(x, y)
E
kf − gk22 =
E
x∈{0,1}J

y∈{0,1}J

h h

ii
= kf − fJ k22 + kfJ − gk22 + 2 E E f (x, y) − fJ (x, y) fJ (x, y) − g(x, y) .
x

y

Since fJ − g is a J-junta, it does not depend on y and, by the definition of fJ , the last term equals
0. Therefore, kf − gk22 = kf − fJ k22 + kfJ − gk22 and the claim follows.
The property P ⊆ Fn is a property of k-juntas if every function f ∈ P is a k-junta. The core
property of a property P of k-juntas is the property Pcore ⊆ Fk defined by Pcore = {fcore : f ∈ P}.
For any γ > 0, the γ-discretized approximation of a function f ∈ Fn is the function f (γ) obtained
by rounding the value f (x) for each x ∈ {0, 1}n to the nearest multiple of γ. The γ-discretized
approximation of a property P is the property P (γ) = {f (γ) : f ∈ P}.

2.3

Influence

The notion of influence of coordinates in functions over the Boolean hypercube plays a central role
in both our algorithm and its analysis. Informally, the influence of a set of coordinate measures
how much re-randomizing these coordinates affects the value of the function. This notion is made
precise as follows.
Definition 2.5. The influence of a set S ⊆ [n] of coordinates in the function f : {0, 1}n → [0, 1] is
h
h


2 ii
Var f (x, y) = 21
E
.
E
f (x, y) − f (x, y ′ )
Inf f (S) :=
E
x∈{0,1}S

y∈{0,1}S

x∈{0,1}S

y,y ′ ∈{0,1}S

Our proofs make use of a few standard facts regarding the influence of sets of coordinates in f .
P
Fact 2.6. The influence of S ⊆ [n] in f ∈ Fn is Inf f (S) = T :T ∩S6=∅ fˆ2 (T ).

Fact 2.7. For every f ∈ Fn and S, T ⊆ [n], we have Inf f (S) ≤ Inf f (S ∪ T ) ≤ Inf f (S) + Inf f (T ).
Fact 2.8. For every f ∈ Fn and J ⊆ [n], we have Inf f (J ) = dist2 (f, fJ )2 .

Proposition 2.9. Fix ǫ > 0, and let f, g : {0, 1}n → [0, 1] satisfy dist2 (f, g) ≤ ǫ. Then for any set
1
1
S ⊆ [n], |Inf f (S) 2 − Inf g (S) 2 | ≤ ǫ.
1

1

Proof. By Fact 2.8, we have Inf f (S) 2 = kf − fS k2 and Inf g (S) 2 = kg − gS k2 . By Proposition 2.4,
we also have that kf −fS k2 ≤ kf −gS k2 . Combining these observations with the triangle inequality,
1
1
we obtain Inf f (S) 2 − Inf g (S) 2 = kf − fS k2 − kg − gS k2 ≤ kf − gS k2 − kg − gS k2 ≤ kf − gk2 ≤ ǫ.
1
1
1
1
Hence Inf f (S) 2 − Inf g (S) 2 ≤ ǫ and, similarly, Inf g (S) 2 − Inf f (S) 2 ≤ ǫ as well.
Proposition 2.10. There is an algorithm EstimateInf such that for every f : {0, 1}n → [0, 1],
S ⊆ [n], m ≥ 1, and t ≥ 0, it makes m queries to f and returns an estimate of the influence of S
in f that satisfies


2
Pr |Inf f (S) − EstimateInf(f, S, m)| ≥ t ≤ 2e−2mt .
7

Algorithm 1: Implicit Learning Tester(F, k, ǫ)
O(k)

1
2
3
4
5
6
7
8
9
10
11
12

6

k

2
Data: q = 2 ǫ5 , m = O( kǫ5 ), r = log 100k
4
Draw x(1) , . . . , x(q) ∈ {0, 1}n independently and uniformly at random;

(1)
(q) 
For each c ∈ {0, 1}q , define Sc ← i ∈ [n] : xi , . . . , xi
=c ;

Let P1 , . . . , P100k4 be a random equi-partition of {0, 1}q ;
4
for each JS⊆ [100k
S ] of size |J| = k do
SJ ← j∈J c∈Pj Sc ;
ηJ ← EstimateInf(f, [n] \ SJ , m);
∗
{j1 , . . . , jk∗ } ← argminJ ηJ ;
(P0,1 , . . . , P0,k ) ← (Pj1∗ , . . . , Pjk∗ );

for ℓ = 1, . . . , r do
Let Pℓ,i,0 , Pℓ,i,1 be a random equi-partition of Pℓ−1,i for each i ≤ k;
k
for every S
z ∈ {0,
S 1} do
Sz ← i≤k c∈Pℓ,i,z Sc ;
i

13
14
15
16
17
18
19
20
21

ηz ← EstimateInf(f, [n] \ Sz , m);
∗
zℓ ← argminz ηz ;
For each i ≤ k, update Pℓ,i ← Pℓ,i,zℓ∗ ;
S
Let B = {b1 , ..., bk } ← i≤k Pr,i ;
If EstimateInf(f, [n] \ SB , m) > ǫ2 /1000, reject;
Let φ : {0, 1}n → {0, 1}k be any projection that satisfies φ(x)i ∈ Sbi for each i ≤ k;
(

ǫ

)

1000
for h ∈ Fcore
do
2
P
q
1
If q i=1 f (x(i) ) − h(φ(x(i) )) ≤ 0.35ǫ, accept and return h;
Reject;

We also use the following key lemma from [6].
Lemma 2.11 (Lemma 2.3 in [6]). Let f : {0, 1}n → [0, 1] be a function that is ǫ-far from kjuntas and P be a random partition of [n] into r > 20k2 parts. Then with probability at least 56 ,
2
Inf f (J) ≥ ε4 for any union J of k parts from P .
For the reader’s convenience, we include the proof of Lemma 2.11 in Appendix A; though
the original lemma in [6] was only for Boolean-valued functions, the proof remains essentially
unchanged.

3

Testing by implicit learning

The proof of Theorem 1.3 is established by analyzing the Implicit Learning Tester algorithm.

8

3.1

Proof of Theorem 1.3

The analysis of the Implicit Learning Tester relies on two technical lemmas. The first shows
that when the input function f is close to a k-junta, then with reasonably large probability, the
function f is close to a junta on the set B of k parts that is identified by the algorithm.
Lemma 3.1. For any ε > 0, if the function f : {0, 1}n → [0, 1] is ε-close to a k-junta and every
ε2
call to EstimateInf returns an influence estimate with additive
error at most 100k

 2 , 1then the set
2
B obtained by the Junta-Property Tester satisfies Pr Inf f ([n] \ SB ) > 100ε ≤ 20 .

The second lemma shows that the estimate in Step 20 provides a good estimate of the distance
between f and the functions in P.
Lemma 3.2. Fix ε > 0. Let f : {0, 1}n → [0, 1] be a function that satisfies dist2 (f, g) ≤ ε for
(

ε

)

1000
some function g that is a junta on J ⊆ [n], |J| ≤ k. Then for every hcore ∈ Fcore
, the mapping
n
k
ψ : {0, 1} → {0, 1} defined in the Implicit Learning Tester and the function h = hcore ◦ ψ
satisfy
q
 X
 1
(i)
(i) 2 2
1
− dist2 (g, h) ≤ 3ε
f
(x
))
−
h(x
)
q

i

4

except with probability at most 2e−16qε +

5k 2
2q .

The proofs of these lemmas are presented in Sections 3.2 and 3.3. We now show how they are
used to complete the proof of Theorem 1.3.
As a first observation, we note that by Hoeffding’s inequality and the union bound, all of the
2
calls to EstimateInf have additive error at most 10ǫ6 k2 except with probability at most 61 . In the
following, we assume that this condition holds and show how, when it does, the algorithm correctly
accepts or rejects with probability with probability at least 65 .
Claim 3.3 (Completeness). When f is 10ǫ6 -close to the property F of k-juntas, the Implicit
Learning Tester accepts with probability at least 65 .
Proof. First, by Lemma 3.1, the probability that f is rejected on step 17 is at most

1
18 .

In the rest
(

ǫ

)

1000
of the proof, we will show that except with probability at most 19 , there is a function hcore ∈ Fcore
for which the algorithm accepts on line 20.
Let g ∈ F be a function that satisfies dist2 (f, g) ≤ 10ǫ 6 . Without loss of generality, we can
assume that g is a junta on [k]. Let J = [k] ∩ SB be the set of the junta variables of g that
are contained in the final parts selected by the algorithm. Again without loss of generality (by
relabeling the input variables once again if necessary), we can assume that J = [j] for some j ≤ k,
and i ∈ Sbi , for i ≤ j.
Define ψ : {0, 1}n → {0, 1}k to be the mapping defined by ψ(x) = (x1 , . . . , xj , xi1 , . . . , xik−j )
where i1 , . . . , ik−j ∈ [n] \ [k] are representative coordinates from the remaining parts b ∈ B for
which Pb ∩ [k] = ∅.
Let gcore ∈ Fcore be the core of g corresponding to the projection ψ(x) = (x1 , . . . , xk ), and let

(

ǫ

)

106
be the discretized approximation to gcore . Define h = hcore ◦ ψ. By our choice of g,
hcore ∈ Fcore
we have dist2 (f, g) ≤ 10ǫ 6 . In order to invoke Lemma 3.2, we now want to bound dist2 (g, h).

9

ǫ

Let h∗ ∈ F ( 106 ) , be the discretized approximation of g. Then dist2 (g, h∗ ) ≤
inequality implies that
dist2 (f, h∗ ) ≤ dist2 (f, g) + dist2 (g, h∗ ) ≤

ǫ
106

and the triangle

2ǫ
106

and that
dist2 (g, h) ≤ dist2 (g, h∗ ) + dist2 (h∗ , h) ≤ dist2 (h∗ , h) +

ǫ
.
106

Furthermore, since hcore = h∗core ,
h
2 1
dist2 (h∗ , h) = E h∗core (x1 , . . . , xk ) − h∗core (x1 , . . . , xj , xi1 , . . . , xik−j ) ] 2
x

1

1

= 2 Inf h∗core ([k] \ [j]) 2 = 2 Inf h∗ ([n] \ [j]) 2 .

By Proposition 2.9 and Lemma 3.1, except with probability at most
1

1
18 ,

1

1

Inf h∗ ([n] \ [j]) 2 ≤ Inf f ([n] \ [j]) 2 + dist2 (f, h∗ ) ≤ Inf f ([n] \ SB ) 2 +

2ǫ
106

≤

12ǫ
106

13
and the distance between g and h is bounded by dist2 (g, h) ≤ 10
6 ǫ. When this bound holds, by
ǫ
1
Lemma 3.2 with ε = 100 , the algorithm accepts f for this h except with probability at most 18
.
ǫ
Claim 3.4 (Soundness I). If f is 100
-far from being a k-junta, then the Implicit Learning
Tester rejects with probability at least 56 .

Proof. The initial partition SP1 , . . . , SP100k4 is a random partition of [n] with more than 20k2 parts
so, by Lemma 2.11, with probability at least 56 , for any union J ⊆ [n] of at most k of these parts
ǫ2
we have Inf f ([n] \ J) ≥ 400
. When this is the case, the inclusion SB ⊆ L0 and the fact that L0 is
the complement of the union of some set of k parts in the random partition imply that
ǫ2
400

Inf f ([n] \ SB ) ≥ Inf f (L0 ) ≥

and, under the assumed accuracy of EstimateInf calls, the algorithm rejects f in Step 17.
ǫ
-close to a k-junta, but is
Claim 3.5 (Soundness II). If f is 100
Learning Tester rejects with probability at least 65 .

99ǫ
100 -far

from F, then the Implicit
(

ǫ

)

ǫ
1000
. For any hcore ∈ Fcore
and any
Proof. Let g be any k-junta that satisfies dist2 (f, g) ≤ 100
ǫ
( 1000 )
n
k
injective mapping ψ : {0, 1} → {0, 1} , the function h = hcore ◦ ψ is in F
and so by the
triangle inequality,
ǫ
ǫ
dist2 (f, F ( 1000 ) ) ≥ dist2 (f, F) − 1000

and
dist2 (g, h) ≥ dist2 (f, h) − dist2 (f, g) ≥

99
100 ǫ
(

−
ǫ

)

ǫ
1000

−

ǫ
100

≥

97
100 ǫ.
k

(

ǫ

)

1000
1000
Then, by Proposition 2.9 and the union bound over all |Fcore
| ≤ (1000/ǫ)2 functions in Fcore
,
5
with probability at least 6 , the condition in Step 20 is never satisfied and the algorithm rejects.

10

To complete the proof of Theorem 1.3 in the case where p = 2, consider now any property P that
contains only functions which are 10ǫ 6 -close to some k-junta. Let F be the property that includes
all k-juntas that are 10ǫ6 -close to P. Claim 3.3 shows that Implicit Learning Tester accepts
every function in P with the desired probability, and Claims 3.4 and 3.5 shows that it rejects all
functions that are ǫ-far from P. Finally, we note that the query complexity of the algorithm is
O(k log k)
at most q + 2m(2O(k log(k)) + 2k q) = 2 ǫ10 , as claimed. Finally, the general result for ℓp testing
when p 6= 2 follows from Fact 2.1.

3.2

Proof of Lemma 3.1

Let f be any function ε-close to a k-junta and assume without loss of generality (by relabeling the
input variables if necessary) that f is close to a junta on [k]. The definition of P1 , . . . , P100k4 in step
3, means that SP1 , . . . , SP100k4 is a random partition of [n]. So by the union bound, the probability
1
that any two of the coordinates in [k] land in the same part is at most 100k
2.
Sk
For each ℓ = 0, 1, 2, . . . , r, let Lℓ = [n] \ i=1 SPℓ,i denote the set of variables that have been
“eliminated” after ℓ iterations of the loop. Then [n] \ SB = Lr and
r 

X
Inf f (Lℓ ) − Inf f (Lℓ−1 ) .
(1)
Inf f ([n] \ SB ) = Inf f (L0 ) +
ℓ=1

We bound both terms on the right-hand side of the expression separately.
By Proposition 2.9, we have Inf f ([n] \ [k]) ≤ ε2 and so by the monotonicity of influence there
is a choice of J ⊆ [k2 ] of size |J| ≤ k for which Inf f ([n] \ SJ ) ≤ ε2 . The guaranteed accuracy on
EstimateInf then implies that
2
2
(2)
Inf f (L0 ) ≤ (1 + 100k
2 )ε .
Define E = {ℓ ≤ r : (Lℓ \ Lℓ−1 ) ∩ [k] 6= ∅} to be the set of rounds for which the algorithm
eliminated at least one of the coordinates in [k]. By this definition, each ℓ ∈ [r] \ E satisfies
(Lℓ \ Lℓ−1 ) ∩ [k] = ∅ and
X
X
X
fˆ(T )2
Inf f (Lℓ ) − Inf f (Lℓ−1 ) =
ℓ∈[r]\E T : T ∩Lℓ 6=∅∧T ∩Lℓ−1 =∅

ℓ∈[r]\E

≤

X

fˆ(T )2 ≤ Inf f ([n] \ [k]) ≤ ε2 .

(3)

T ⊆[n]\[k]

For each ℓ ∈ E, define Xℓ = {∪ki=1 SPℓ,i,1−(z∗ ) : SPℓ,i,1−(z∗ ) ∩ [k] 6= ∅} to be the set of coordinates
ℓ i
ℓ i
in the parts that contain a coordinate in [k] that was eliminated in the ℓth iteration of the loop.
Let also Yℓ = {∪ki=1 SPℓ,i,(z∗ ) : SPℓ,i,1−(z∗ ) ∩ [k] 6= ∅} be the coordinates in the parts that were kept
ℓ i
ℓ i
instead. Then the guaranteed accuracy of EstimateInf and the choice of zℓ∗ implies that

ε2
Inf f (Lℓ ) ≤ Inf f (Lℓ \ Xℓ ) ∪ Yℓ + 2 100k
2

and, therefore,
X
X

2ε2
+
Inf f (Lℓ \ Xℓ ) ∪ Yℓ − Inf f (Lℓ−1 )
Inf f (Lℓ ) − Inf f (Lℓ−1 ) ≤
1000k
ℓ∈E

ℓ∈E

≤

2ε2

1000k

+

X

fˆ(T )2 +

X

ℓ∈E T : T ∩(Lℓ \Xℓ )6=∅∧T ∩Lℓ−1 =∅

11

X

X

ℓ∈E T : T ∩Yℓ 6=∅∧T ∩Lℓ−1 =∅

fˆ(T )2 .

(4)

As above, since (Lℓ \ Xℓ ) ∩ [k] = ∅,
X
X

fˆ(T )2 ≤

ℓ∈E T : T ∩(Lℓ \Xℓ )6=∅∧T ∩Lℓ−1 =∅

X

fˆ(T )2 ≤ ε2 .

(5)

T ⊆[n]\[k]

It remains to bound the last sum on the right-hand side of (4). By splitting up the terms in this
sum according to whether |T | ≤ k or not, we obtain
X
X
X
fˆ(T )2 · 1[T ∩ Lℓ−1 = ∅].
fˆ(T )2 · 1[T ∩ Yℓ 6= ∅] +
fˆ(T )2 ≤
T :T ∩Yℓ 6=∅∧T ∩Lℓ−1 =∅

|T |>k

|T |≤k

Let Z ⊆ [n]\[k] denote the set of coordinates that occur in one of the the original parts SP1 , . . . , SP100k4
that also contains one of the elements in [k]. Then Yℓ ⊆ Z and
X
X X
X X
fˆ(T )2 · 1[T ∩ Z 6= ∅].
fˆ(T )2 · 1[T ∩ Z 6= ∅] ≤ k ·
fˆ(T )2 · 1[T ∩ Yℓ 6= ∅] ≤
ℓ∈E |T |≤k

ℓ∈E |T |≤k

|T |≤k

The probability, over the choice of P1 , . . . , P100k4 , that T ∩ Z 6= ∅ is at most |T |/100k 3 , so the
expected value of the last expression (again over the choice of the initial partition) is bounded
above by
E

hX X

ℓ∈E |T |≤k

i
fˆ(T )2 · 1[T ∩ Yℓ 6= ∅] ≤ k ·

fˆ(T )2 ·

X

|T |≤k,T \[k]6=∅



k 
ε2
1
·
Inf
([n]
\
[k])
≤
.
≤
f
100k3
100k
100k
(6)

Lastly, since L0 ⊆ Lℓ−1 for each ℓ ≥ 1,
X
X
fˆ(T )2 · 1[T ∩ L0 = ∅].
fˆ(T )2 · 1[T ∩ Lℓ−1 = ∅] ≤
|T |>k

|T |>k

A set T can be disjoint from L0 only when its elements are contained in at most k of the parts of
1
the initial random partition, which happens with probability at most 100k
2 when |T | > k, so
E

hX X

ℓ∈E |T |>k

i
i
h X
fˆ(T )2 · 1[T ∩ L0 = ∅] ≤
fˆ(T )2 · 1[T ∩ Lℓ−1 = ∅] ≤ E k
|T |>k

1 X ˆ 2
ε2
f (T ) ≤
,
100k
100k
|T |>k

(7)
P
where the last inequality uses the fact that |T |>k fˆ(T )2 ≤ Inf f ([n] \ [k]).
Combining the inequalities (1)–(7), we obtain that the expected value of Inf f ([n]\SB ) is bounded
above by


2
2
2
2ε2
2
2
E Inf f ([n] \ SB ) ≤ (1 + 100k
2 )ε + 100k + (1 + 100k )2ε ≤ 4ε .
Applying Markov’s inequality and adding the probability that the junta variables are completely
separated in the partition P1 , . . . , P100k4 completes the proof of the lemma.

3.3

Proof of Lemma 3.2

 P
2 1/2
denote the
For any X = (x(1) , . . . , x(q) ), let distX (f1 , f2 ) = 1q qi=1 f1 (x(i) ) − f2 (x(i) )
empirical distance between f1 and f2 according to X. To prove the lemma, we want to show that
distX (f, h) is within the specified bounds.
12

The function distX is a metric, so we can apply the triangle inequality to obtain
distX (f, h) ≤ distX (f, g) + distX (g, h).
By Hoeffding’s inequality, when x(1) , . . . , x(q) are drawn independently and uniformly at random,
the upper bound
distX (f, g) ≤ dist2 (f, g) + ε ≤ 2ε
4

holds except with probability at most e−16qε .
We now want to show that distX (g, h) is also close to dist2 (g, h). This analysis is a bit more
subtle, however, because the choice of samples x(1) , . . . , x(q) is not independent of h (as it affects
what mapping ψ will be chosen by the algorithm). So before we can apply concentration inequalities,
we must “decouple” X and h. To do so, we introduce a new random process for generating X. Let
λ : [n] → {0, 1}q be chosen uniformly at random. This function corresponds to a random partition
of the set [n] of coordinates into 2q parts. Let π : {0, 1}q → {0, 1}q be a random permutation. Then
(i)
the random variable X obtained by setting xj = π(λ(j))i has the desired uniform distribution
n
over sequences of q vectors in {0, 1} .
This random process is designed so that the choice of ψ in the algorithm (and therefore also
h) is independent of π; the only information about X used in determining it is the identity of the
parts defined by λ, not what values the coordinates in each parts receive on the q queries. Then
E[distX (g, h)] = E [E[distX (g, h)]]
λ,r π

X

where r represents the internal randomness of the algorithm outside of that used to generate X.
With probability at least k2 /2q , the partition λ completely separates the indices in J. Fix such
a partition λ. Define J ∗ = J ∪ supp(ψ). Then |J ∗ | ≤ 2k. Define Y = (y (1) , . . . , y (q) ) by setting
(i)
y (i) = xJ ∗ . Since distX (g, h) only depend on the coordinates in J ∗ , we can write it equivalently as
distY (g, h).
Let D denote the distribution on Y induced by π. The distribution D is close to but not equal
∗
to the uniform distribution U on {0, 1}q×|J | , since D is equivalent to the distribution obtained by
(1)
(q)
making drawing (yi , . . . , yi ) for each i ∈ J ∗ without replacement from {0, 1}q . Then
Pr [|distY (g, h) − E distY (g, h)| ≥ ε] ≤ dTV (D, U ) + Pr [|distY (g, h) − E distY (g, h)| ≥ ε]

Y ∼D

Y ∼U

≤

4k 2
2q

−16qε4

+e

Y ∼U

Y ∼U

.

2

is by the standard total variation bound
In the last inequality, the bound dTV (D, U ) ≤ (2k)
2q
between sampling with and without replacement [19] and the other bound on the other term is by
Hoeffding’s inequality.

4

Applications

In this short section, we show how Theorems 1.1 and 1.2 both follow directly from Theorem 1.3
and the junta theorem of Feldman and Vondrák.
Proof of Theorem 1.1. By the first part of the Feldman–Vondrák junta theorem, every submodular
function f ∈ Fn is 10ǫ6 -close to a k-junta for some k = O( ǫ12 log 1ǫ ). Therefore, by Theorem 1.3,
13

2

submodularity can be tested with 2O(k log k) /ǫ10 = 2Õ(1/ǫ ) queries in the ℓ2 testing model. By
Fact 2.1, the number of queries for testing submodularity in the ℓp testing model for any 1 ≤ p < 2
2
p/2 2
p
is also 2Õ(1/ǫ ) and for any p > 2 it is 2Õ(1/(ǫ ) ) = 2Õ(1/ǫ ) .
Proof of Theorem 1.2. By Lemma 2.2, additive functions, coverage functions, unit demand functions, OXS functions, and gross substitute functions are all also submodular. Therefore, the first
part of the Feldman–Vondrák junta theorem also applies to these functions and the rest of the
proof is identical to that of Theorem 1.1.
Lemma 2.2 also implies that fractionally subadditive functions are self-bounding, so the second
part of the Feldman–Vondrák junta theorem shows that every function f that has either of these
1
properties is 10ǫ6 -close to a k-junta for some k = 2O( ǫ2 ) . Therefore, by Theorem 1.3, fractional
Õ(1/ǫ2 )

subadditivity and self-boundedness can both be tested with 2O(k log k) /ǫ10 = 22
queries in the
ℓ2 testing model; the general result for the ℓp testing model again follows directly from Fact 2.1.

References
[1] Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and
Tim Roughgarden. Sketching valuation functions. In Proceedings of the Twenty-Third Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19,
2012, pages 1025–1035, 2012.
[2] Maria-Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning valuation
functions. In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27,
2012, Edinburgh, Scotland, pages 4.1–4.24, 2012.
[3] Maria-Florina Balcan and Nicholas J. A. Harvey. Learning submodular functions. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA,
6-8 June 2011, pages 793–802, 2011.
[4] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lp -testing. In Symposium
on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages
164–173, 2014.
[5] Eric Blais. Testing juntas nearly optimally. In Proceedings of the 41st Annual ACM Symposium
on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages
151–158, 2009.
[6] Eric Blais, Amit Weinstein, and Yuichi Yoshida. Partially symmetric functions are efficiently
isomorphism testable. SIAM J. Comput., 44(2):411–432, 2015.
[7] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications
to numerical problems. J. Comput. Syst. Sci., 47(3):549–595, 1993.
[8] Deeparnab Chakrabarty and Zhiyi Huang. Recognizing coverage functions. SIAM Journal on
Discrete Mathematics, 29(3):1585–1599, 2015.

14

[9] Sourav Chakraborty, David Garcı́a-Soriano, and Arie Matsliah. Efficient sample extractors
for juntas with applications. In Automata, Languages and Programming - 38th International
Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, pages
545–556, 2011.
[10] Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A.
Servedio, and Andrew Wan. Testing for concise representations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence,
RI, USA, Proceedings, pages 549–558, 2007.
[11] Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, and Andrew Wan. Efficiently testing sparse GF(2) polynomials. In Automata, Languages and Programming, 35th
International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part
I: Tack A: Algorithms, Automata, Complexity, and Games, pages 502–514, 2008.
[12] Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals
of Mathematics, 162:2005, 2004.
[13] Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM J. Comput.,
39(1):122–142, 2009.
[14] Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular
functions. SIAM J. Comput., 40(4):1133–1153, 2011.
[15] Vitaly Feldman and Pravesh Kothari. Learning coverage functions and private release of
marginals. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona,
Spain, June 13-15, 2014, pages 679–702, 2014.
[16] Vitaly Feldman and Jan Vondrák. Tight bounds on low-degree spectral concentration of
submodular and XOS functions. In IEEE 56th Annual Symposium on Foundations of Computer
Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 923–942, 2015.
[17] Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and XOS
functions by juntas. SIAM J. Comput., 45(3):1129–1170, 2016.
[18] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas.
J. Comput. Syst. Sci., 68(4):753–787, 2004.
[19] David Freedman. A remark on the difference between sampling with and without replacement.
Journal of the American Statistical Association, 72(359):681–681, 1977.
[20] Ehud Friedgut. On the measure of intersecting families, uniqueness and stability. Combinatorica, 28(5):503–528, 2008.
[21] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to
learning and approximation. J. ACM, 45(4):653–750, 1998.
[22] Parikshit Gopalan, Ryan O’Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer.
Testing fourier dimensionality and sparsity. SIAM J. Comput., 40(4):1075–1100, 2011.

15

[23] Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270–296, 2006.
[24] Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. Testing halfspaces.
SIAM J. Comput., 39(5):2004–2047, 2010.
[25] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
[26] Michal Parnas, Dana Ron, and Alex Samorodnitsky. Testing basic boolean formulae. SIAM
J. Discrete Math., 16(1):20–46, 2002.
[27] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications
to program testing. SIAM J. Comput., 25(2):252–271, 1996.
[28] Rocco A. Servedio. Testing by implicit learning: A brief survey. In Property Testing - Current
Research and Surveys, pages 197–210, 2010.
[29] C. Seshadhri and Jan Vondrák. Is submodularity testable? In Innovations in Computer
Science - ICS 2010, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings,
pages 195–210, 2011.

A

Missing proofs from Section 2

We begin with the proof of Lemma 2.11. We emphasize that the proof below is essentially as found
in [6]; the reason we include it here is that the original statement of the proof only applied to
Boolean-valued functions. As we see below, however, the same argument also holds for real-valued
functions.
Theorem A.1. (Dinur and Safra [12]; Friedgut [20]) Let G be a t-intersecting family of subsets of
1
, the p-biased measure of G is bounded by µp (G) ≤ pt .
[n] for some t ≥ 1. For any p < t+1
Proof of Lemma 2.11. For 0 ≤ t ≤ 12 , let Gt = {J ⊆ [n] : Inf f (J) < tε2 } be the family of all the
sets whose compliments have influence less than tε2 . For any two sets J, K ∈ G 1 , the subadditivity
2
of influence implies that
Inf f (J ∩ K) = Inf f (J ∪ K) ≤ Inf f (J) + Inf f (K) < ε2 .
But f is ε-far from every k-junta, so for any two sets J, K ∈ G 1 , |J∩K| > k, from Proposition 2.9.
2
Which means G 1 is a k + 1 intersecting family. There are two cases now, first one is, there is at
2
least one set J ∈ G 1 such that |J| < 2k, second one is all the sets J ∈ G 1 will have |J| ≥ 2k. We
2
2
will show that in both the cases our lemma holds. In the first case let J ∈ G 1 be a set which has
2
fewer than 2k elements, with high probability the set J is completely separated by the partition P,
and we know that for any K ∈ G 1 , |J ∩ K| ≥ k + 1, which means K is not covered by any union
2

2

2

of k-parts in P. Therefore, Inf f (J ) ≥ ε2 > ε4 as we wanted to show.
Consider the case where, all the sets in G 1 have more than 2k elements. Then G 1 is a 2k
2
4
intersecting family. Otherwise, if there are two sets J, K ∈ G 1 such that |J ∩ K| < 2k, then
Inf f (J ∩ K) ≤ Inf f (J) + Inf f (K) <

ε2
4

+

ε2
4

<

ε2
2,

4

thus contradicting our assumption.

16

Let J ⊆ [n] be the union of k parts in P. Since P is a random partition, J is a random subset
1
.
obtained by including each element of [n] in J independently with probability p = kr < 2k+1
By Theorem A.1, PrP [If (J) <

ε2
4]

= Pr[J ∈ G 1 ] = µ k (G 1 ) ≤ ( kr )2k . By the union bound the
4

4

r

probability that there exists a set J ⊆ [n] that is the union of k parts in P for which Inf f (J) <

k k 2k ≤ ( ek )k < 1 .
is bounded above by kr ( kr )2k ≤ ( er
k ) (r)
r
6

ε2
4

The proof of Proposition 2.10 is obtained by considering the EstimateInf algorithm below.

Algorithm 2: EstimateInf(f, S, m)
1
2
3

Draw x1 , . . . , xm uniformly and independently at random from {0, 1}S ;
′ uniformly and independently at random from {0, 1}S ;
Draw y1 , . . . , ym , y1′ , . . . , ym

P
m
1
′ 2
Return 2m
i=1 f (xi , yi ) − f (xi , yi ) ;

The concentration of the estimated influence is obtained via the following (standard) version of
Hoeffding’s inequality.
Hoeffding’s inequality. Let X1 , ..., Xn be independent random variables bounded by a1 ≤ Xi ≤ bi .
Let X = X1 + X2 + · · · Xn have expected value E[X] = µ. Then for any t > 0,
− Pn

Pr[|X − µ| ≥ t] ≤ 2e

17

2t2
(bi −ai )2

i=1

.

