Authors Jean Bourgain, Jeff Kahn, Gil Kalai,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13
www.theoryofcomputing.org
S PECIAL ISSUE : A NALYSIS OF B OOLEAN F UNCTIONS
Influential Coalitions for Boolean
Functions I: Constructions
Jean Bourgain∗ Jeff Kahn† Gil Kalai‡
Received February 16, 2013; Revised October 12, 2020; Published September 30, 2024
Abstract. For 𝑓 : {0, 1} 𝑛 → {0, 1} and 𝑆 ⊂ {1, 2, , . . . , , 𝑛}, let 𝐽𝑆+ ( 𝑓 ) be the probability
that, for 𝑥 uniform from {0, 1} 𝑛 , there is some 𝑦 ∈ {0, 1} 𝑛 with 𝑓 (𝑦) = 1 and 𝑥 ≡ 𝑦
outside 𝑆. We are interested in estimating, for given 𝜇( 𝑓 ) (:= 𝔼( 𝑓 )) and 𝑚, the least
possible value of max{𝐽𝑆+ ( 𝑓 ) : |𝑆| = 𝑚}.
A theorem of Kahn, Kalai, and Linial (KKL) gave some understanding of this
issue and led to several stronger conjectures. Here we disprove a pair of conjectures
from the late 80s, as follows.
(1) The KKL Theorem implies that there is a fixed 𝛼 > 0 so that if 𝜇( 𝑓 ) ≈ 1/2, and
𝑐 > 0, then there is a set 𝑆 of size at most 𝛼𝑐𝑛 with 𝐽𝑆+ ( 𝑓 ) ≥ 1 − 𝑛 −𝑐 . We show that
for every 𝛿 > 0 there is an 𝑓 with 𝜇( 𝑓 ) ≈ 1/2 and 𝐽𝑆+ ( 𝑓 ) ≤ 1 − 𝑛 −𝐶 for every 𝑆 of size
(1/2 − 𝛿)𝑛, where 𝐶 = 𝐶 𝛿 . This disproves a conjecture of Benny Chor from 1989.
(2) We also show that for fixed 𝛿 > 0 there are 𝑐, 𝛼 > 0 and Boolean functions 𝑓 such
that 𝜇( 𝑓 ) > exp[−𝑛 1−𝑐 ] and 𝐽𝑆+ ( 𝑓 ) ≤ exp[−𝑛 𝛼 ] for each 𝑆 of size (1/2 − 𝛿)𝑛. This
disproves a conjecture of the third author from the late 80s.
∗ Supported in part by NSF Grant DMS 1301619.
† Supported by NSF grant DMS0701175 and BSF grant 2006066.
‡ Supported by BSF grant 2006066, ERC advanced grants 320924 and 834735, and NSF grant DMS-1300120.
ACM Classification: G.2.1, G.2.m
AMS Classification: 05D05, 68R05, 60C05
Key words and phrases: Boolean functions, influence, trace of set-systems, discrete isoperimetric
inequalities, tribes
© 2024 Jean Bourgain, Jeff Kahn, and Gil Kalai
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc2024.v020a004
J EAN B OURGAIN , J EFF K AHN , AND G IL K ALAI
1 Introduction
For a set 𝑇 we use Ω(𝑇) for the discrete cube {0, 1}𝑇 and 𝜇𝑇 for the uniform probability measure
on Ω(𝑇). In this paper 𝑓 will always be a Boolean function on Ω([𝑛]) (that is, 𝑓 : Ω([𝑛]) → {0, 1},
where, as usual, [𝑛] = {1, . . . , 𝑛}). We write 𝜇 for 𝜇[𝑛] and 𝜇( 𝑓 ) = 𝜇({𝑥 : 𝑓 (𝑥) = 1})). We reserve
𝑥, 𝑦 for elements of Ω([𝑛]) and set |𝑥| = 𝑥 𝑖 .
Í
Following Ben-Or and Linial [3] we define, for a given 𝑓 and 𝑆 ⊂ [𝑛], the influence of 𝑆 toward
one to be
𝐼𝑆+ ( 𝑓 ) = 𝜇[𝑛]\𝑆 ({𝑢 ∈ Ω([𝑛]\𝑆) : ∃𝑣 ∈ Ω(𝑆), 𝑓 (𝑢, 𝑣) = 1}) − 𝜇( 𝑓 ). (1.1)
Similarly, the influence of 𝑆 toward zero is
𝐼𝑆− ( 𝑓 ) = 𝜇[𝑛]\𝑆 ({𝑢 ∈ Ω([𝑛]\𝑆) : ∃𝑣 ∈ Ω(𝑆), 𝑓 (𝑢, 𝑣) = 0}) − (1 − 𝜇( 𝑓 )) (1.2)
and the (total) influence of 𝑆 is
𝐼𝑆 ( 𝑓 ) = 𝐼𝑆+ ( 𝑓 ) + 𝐼𝑆− ( 𝑓 ).
Suppose 𝜇( 𝑓 ) = 1/2. It then follows from a theorem of Kahn, Kalai and Linial [12]
(Theorem 2.2 below, henceforth “KKL”) that for every 𝑎 ∈ (0, 1) there is an 𝑆 ⊂ [𝑛] of size 𝑎𝑛
with 𝐼𝑆+ ( 𝑓 ) ≥ 1/2 − 𝑛 −𝑐 , where 𝑐 > 0 depends on 𝑎. (See Theorem 2.3.) Benny Chor conjectured
in 1989 [7] that one can in fact achieve 𝐼𝑆+ ( 𝑓 ) ≥ 1/2 − 𝑐 𝑛 (where, again, 𝑐 < 1 depends on 𝑎). The
conjecture has been “in the air” since that time, though as far as we know it has appeared in
print only in [13, 14].
In this paper we disprove Chor’s conjecture and another, similar conjecture from the same
period. In the subsequent part II, we improve the preceding consequence of KKL.
For our purposes the subtracted terms in equations (1.1) and (1.2) are mostly a distraction,
and it sometimes seems clearer to speak of 𝐽𝑆+ ( 𝑓 ) := 𝐼𝑆+ ( 𝑓 ) + 𝜇( 𝑓 ) and 𝐽𝑆− ( 𝑓 ) := 𝐼𝑆− ( 𝑓 ) + (1 − 𝜇( 𝑓 )).
Thus, for example, 𝐽𝑆+ ( 𝑓 ) is the probability that a uniform setting of the variables in [𝑛] \ 𝑆
doesn’t force 𝑓 = 0, and Chor’s conjecture predicts an 𝑆 with 𝐽𝑆+ ( 𝑓 ) ≥ 1 − 𝑐 𝑛 . The following
statement shows that this need not be the case.
Theorem 1.1. For any fixed 𝛼, 𝛿 ∈ (0, 1) there exists 𝐶 ∈ ℝ such that for all large enough 𝑛 there
exists an 𝑓 such that 𝜇( 𝑓 ) = 𝛼 and 𝐽𝑆+ ( 𝑓 ) < 1 − 𝑛 −𝐶 for every 𝑆 ⊆ [𝑛] of size at most (1/2 − 𝛿)𝑛 .
We should note that one cannot expect to go much beyond |𝑆| = (1/2 − 𝛿)𝑛; for example if
𝜇( 𝑓 ) = 1/2, then it follows from the “Sauer–Shelah Theorem” (Theorem 2.5) that there is an 𝑆 of
size 𝑛/2 with 𝐽𝑆+ ( 𝑓 ) = 1.
Another consequence of KKL (see Theorem 2.4 below) is that there is a 𝛽 > 0 such that for
any 𝑓 with 𝜇( 𝑓 ) > 𝑛 −𝛽 there is an 𝑆 of size (say) 0.1𝑛 with influence 1 − 𝑜(1). A conjecture of the
third author, again from the late 80s, asserts that the same conclusion holds even assuming only
𝜇( 𝑓 ) > (1 − 𝜀)𝑛 for sufficiently small 𝜀. This conjecture turns out to be false as well.
Theorem 1.2. For any fixed 𝜀, 𝛿 > 0 there exists 𝛼 > 0 such that for all large enough 𝑛 there
exists an 𝑓 such that 𝜇( 𝑓 ) > (1 − 𝜀)𝑛 and no set of size at most (1/2 − 𝛿)𝑛 has influence toward 1
more than exp[−𝑛 𝛼 ].
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 2
I NFLUENTIAL C OALITIONS FOR B OOLEAN F UNCTIONS I: C ONSTRUCTIONS
This can be strengthened a bit to require 𝜇( 𝑓 ) > exp[−𝑛 1−𝑐 ] for some fixed 𝑐 = 𝑐 𝛿 > 0.
The examples proving Theorems 1.1 and 1.2 are given in Section 3. Each of these is of
the form 𝑓 = 𝑚 𝑖=1 𝐶 𝑖 , where the 𝐶 𝑖 are random disjunctions of 𝑘 literals using 𝑘 distinct
Ó
variables (henceforth “𝑘-clauses”). These 𝑓 ’s, which may be thought of as variants of the “tribes”
construction of Ben-Or and Linial (see below), were inspired by a paper of Ajtai and Linial [1]
and share with it the following curious feature. It is easy to see that any 𝑓 can be converted to a
monotone (i. e., increasing) 𝑓 0 with 𝔼( 𝑓 0) = 𝜇( 𝑓 ) and each influence (𝐼𝑆+ and so on) for 𝑓 0 no larger
than the corresponding influence for 𝑓 ; thus it is natural to look for 𝑓 ’s with small influences
among the increasing functions. But the present random examples, like those of [1], do not do
this, and it is not easy to see what one gets by monotonizing them.
Improving the consequences of KKL
While the preceding, rather optimistic conjectures turn out to be false, in part II we show that
the first of the aforementioned consequences of KKL can be improved. (The results and proofs
of both parts were given together in the arXiv publication [6].)
Theorem 1.3. For each 𝐶 > 0, there is a 𝛿 > 0 such that for any 𝑓 with 𝜇( 𝑓 ) > 𝑛 −𝐶 , there is an
𝑆 ⊂ [𝑛] of size at most (1/2 − 𝛿)𝑛 with 𝐽𝑆+ ( 𝑓 ) > .9.
(Of course, as elsewhere in this discussion, “.9” could be any preset 𝜌 < 1.)
Note that the gap between Theorems 1.2 and 1.3 is substantial and our modest progress is
likely not the final word on the problem. For example, could it be that there is some fixed 𝛽
such that there are 𝑓 ’s with 𝜇( 𝑓 ) > 𝑛 −𝛽 for which no 𝑆 of size 0.1𝑛 has influence Ω(1)? We will
discuss this question further in the next section.
The Proof of Theorem 1.3 ([6]) goes roughly as follows. We employ two strategies, both
variants of the analysis in [12]. The first uses the total influence, assumed sufficiently large.
If at some point this total influence becomes “small,” we switch to a different procedure that
combines the incremental argument from [12] with the Sauer–Shelah theorem.
2 Background and perspective
Influence
We write 𝐼ℓ ( 𝑓 ) for 𝐼{ℓ } ( 𝑓 ). A form of the classic edge isoperimetric inequality for Boolean
functions is
Theorem 2.1. For any (Boolean function) 𝑓 with 𝜇( 𝑓 ) = 𝑡,
𝑛
Õ
𝐼( 𝑓 ) := 𝐼ℓ ( 𝑓 ) ≥ 2𝑡 log2 (1/𝑡). (2.1)
𝑘=1
(This convenient version is easily derived from the precise statement, due to Hart [9]; see also
[11, Sec. 7] for a simple inductive proof.)
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 3
J EAN B OURGAIN , J EFF K AHN , AND G IL K ALAI
While (2.1) is exact or close to exact (depending on 𝑡), it typically gives only a weak lower bound
on the maximum of the 𝐼ℓ ( 𝑓 )’s, namely
max 𝐼ℓ ( 𝑓 ) ≥ 2𝑡 log2 (1/𝑡)/𝑛. (2.2)
ℓ
For 𝑡 not too close to 0 or 1, the following statement from [12] gives better information.
Theorem 2.2 (KKL). There is a fixed 𝑐 > 0 such that for any 𝑓 with 𝜇( 𝑓 ) = 𝑡, there is an ℓ ∈ [𝑛]
with
𝐼ℓ ( 𝑓 ) ≥ 𝑐𝑡(1 − 𝑡) log 𝑛/𝑛. (2.3)
Recall that 𝐽ℓ ( 𝑓 ) = 𝜇( 𝑓 ) + 𝐼ℓ ( 𝑓 ). Repeated application of Theorem 2.2 gives the following two
corollaries.
Theorem 2.3. For all 𝑎, 𝑡 ∈ (0, 1) there is a c such that for any 𝑓 with 𝜇( 𝑓 ) = 𝑡 there is an 𝑆 ⊆ [𝑛]
with |𝑆| ≤ 𝑎𝑛 and
𝐽𝑆+ ( 𝑓 ) ≥ 1 − 𝑛 −𝑐
(that is, 𝐼𝑆+ ( 𝑓 ) ≥ (1 − 𝑡) − 𝑛 −𝑐 ).
Similarly (either by the same argument or by applying Theorem 2.3 to the function 1 − 𝑓 (𝑥))
there is a small 𝑆0 with 𝐽𝑆−0 ( 𝑓 ) ≥ 1 − 𝑛 −𝑐 (i. e., 𝐼𝑆−0 ( 𝑓 ) ≥ 𝑡 − 𝑛 −𝑐 ), and combining these observations
we find that there is in fact a small 𝑆00 (e. g., 𝑆 ∪ 𝑆0) with 𝐼𝑆00 ( 𝑓 ) ≥ 1 − 𝑛 −𝑐 .
Theorem 2.4. For every 𝛿, 𝜖 > 0, there is an 𝛼 > 0 such that for large enough 𝑛 and any 𝑓 with
𝜇( 𝑓 ) ≥ 𝑛 −𝛼 , there is an 𝑆 ⊆ [𝑛] with |𝑆| = 𝛿𝑛 and
𝐽𝑆+ ( 𝑓 ) ≥ 1 − 𝜖.
The conjecture of Chor stated in Section 1 asserts that the 𝑛 −𝑐 in Theorem 2.3 can be replaced by
something exponential in 𝑛, and the conjecture stated before Theorem 1.2 proposes a similar
weakening of the 𝑛 −𝛼 lower bound on 𝜇( 𝑓 ) in Theorem 2.4. As already noted, we will show
below that these conjectures are incorrect.
Tribes
The original “tribes” examples of Ben-Or and Linial [3] are Boolean functions of the form
𝑓 = 𝑚 𝑖=1 𝐶 𝑖 , where the “tribes” 𝐶 𝑖 are conjunctions of 𝑘 (distinct) variables
Ô
Ó𝑚and each variable
belongs to exactly one tribe. The dual of such an 𝑓 (so “dual tribes”) is 𝑔 = 𝑖=1 𝐷𝑖 , where 𝐷𝑖 is
the disjunction of the variables in 𝐶 𝑖 (so again, each variable belongs to exactly one 𝐷𝑖 ).
When 𝑘 = log 𝑛 − log log 𝑛 − log ln(1/𝑡), we have 1 − 𝜇( 𝑓 ) = 𝔼(𝑔) ≈ 𝑡 (where log = log2 and
𝑓 , 𝑔 are as above). For fixed 𝑡 ∈ (0, 1) both constructions show that Theorem 2.2 is sharp (up to
the value of 𝑐).
On the other hand, when 𝑡 = 𝑂(𝑛 −𝑐 ) for a fixed 𝑐 > 0, 𝑓 shows that (2.2) is tight up to a
multiplicative constant, depending on 𝑐; for example, 𝑘 = 2 log 𝑛 − log log 𝑛 gives 𝜇( 𝑓 ) ≈ 1/(2𝑛)
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 4
I NFLUENTIAL C OALITIONS FOR B OOLEAN F UNCTIONS I: C ONSTRUCTIONS
and 𝐼ℓ ( 𝑓 ) ≈ 2 log 𝑛/𝑛 2 = Θ(𝜇( 𝑓 ) log(1/𝜇( 𝑓 ))/𝑛) for each ℓ . (In contrast, for 𝔼(𝑔) ≈ 1/𝑛, we
should take 𝑘 = log 𝑛 − 2 log log 𝑛 − 1, in which case 𝐼ℓ (𝑔) = Θ(log2 𝑛/𝑛 2 ) and (2.2) is off by a
log.)
For 𝑓 (again, as above) with 𝜇( 𝑓 ) ∈ (Ω(1), 1 − Ω(1)), there are sets of size log 𝑛 with
large influence toward 1, while no set of size 𝑜(𝑛/log 𝑛) has influence Ω(1) toward 0. (The
corresponding statement with the roles of 0 and 1 reversed holds for 𝑔.) The Ajtai-Linial
construction mentioned in the introduction shows that there are Boolean functions ℎ with
𝔼(ℎ) ≈ 1/2 and 𝐼𝑆 (ℎ) < 𝑜(1) for every 𝑆 of size 𝑜(𝑛/log2 𝑛).
Trace
We now briefly consider influences from a different point of view. For a set 𝑋 let 2𝑋 = {𝑆 : 𝑆 ⊂ 𝑋},
𝑋 𝑋 𝑛 Í 𝑘−1 𝑛 𝑋
𝑘 = {𝑆 ⊂ 𝑋 : |𝑆| = 𝑘}, <𝑘 = {𝑆 ⊂ 𝑋 : |𝑆| < 𝑘} and <𝑘 = 𝑖=0 𝑖 . For ℱ ⊂ 2 and 𝑌 ⊂ 𝑋,
the trace of ℱ on 𝑌 is
ℱ|𝑌 = {𝑆 ∩ 𝑌 : 𝑆 ∈ ℱ }.
Let 𝑋 = [𝑛]. The “Sauer–Shelah Theorem” (below) determines, for every 𝑛 and 𝑚, the
𝑋
minimum 𝑇 such that for each ℱ ⊆ 2𝑋 of size 𝑇 there is some 𝑌 ∈ 𝑚 on which the trace of ℱ
𝑌
is complete, meaning ℱ|𝑌 = 2 . Such a 𝑌 is said to be shattered by ℱ .
𝑛
Theorem 2.5 (The Sauer–Shelah Theorem). If ℱ ⊂ 2𝑋 and |ℱ | > <𝑟 , then ℱ shatters some
𝑌 ∈ 𝑋𝑟 .
𝑋
, the Hamming ball of radius 𝑟 − 1 about ∅ with respect to
That this is sharp is shown by ℱ = <𝑟
𝑋
the usual Hamming metric on 2 ≡ Ω(𝑋).
Theorem 2.5 was proved around the same time by Sauer [15], Shelah and Perles [16],
and Vapnik and Chervonenkis [17]. It has many connections, applications and extensions in
combinatorics, probability theory, model theory, analysis, statistics and other areas.
We identify Ω([𝑛]) and 2[𝑛] in the usual way. The connection between traces and influences
is as follows. Let 𝑓 be a Boolean function on Ω([𝑛]) and ℱ = 𝑓 −1 (1). It is easy to see that for
𝑆 ⊆ [𝑛] and 𝑇 = [𝑛]\𝑆,
𝐽𝑆+ ( 𝑓 ) = 2−|𝑇 | |ℱ|𝑇 |.
Thus, in the language of traces, we are interested in the effect of relaxing “ℱ shatters 𝑌” to
require only that ℱ|𝑌 contain a large fraction of 2𝑌 .
The following arrow notation (e. g., [5, 8, 2]) is convenient. Write (𝑁 , 𝑛) → (𝑀, 𝑟) if every
ℱ ⊆ 2[𝑛] of size 𝑁 has a trace of size at least 𝑀 on some 𝑆 ∈ [𝑛]
𝑟 ; for example the Sauer–Shelah
𝑛
Theorem says ( <𝑟 + 1, 𝑛) → (2𝑟 , 𝑟).
One might hope that Hamming balls would again give the best examples in our relaxed
setting, which would say, for example, that for 𝑚 ≤ 𝑛,
𝑛 𝑚
+ 1, 𝑛) → ( <𝑟 + 1, 𝑚).
( <𝑟 (2.4)
But (2.4), which was first considered by Bollobás and Radcliffe [4] and would have implied both
of the conjectures disproved here, was shown in [4] to be false for fixed 𝑟 and (large) 𝑚 = 𝑛/2.
(For 𝑟 = 𝑛/2 and 𝑚 = 𝑛 − 1, it fails for the original tribes example discussed above.)
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 5
J EAN B OURGAIN , J EFF K AHN , AND G IL K ALAI
Two problems
Question 2.1. For fixed 𝛼, 𝛿 > 0, what is the largest 𝑡 ∈ (0, 1/2) for which one can find Boolean
functions 𝑓 with 𝜇( 𝑓 ) = 𝑡 and 𝐼𝑆+ ( 𝑓 ) < 𝛼 for every 𝑆 ⊆ [𝑛] of size at most (1/2 − 𝛿)𝑛?
As far as we know 𝑡 > 𝑛 −𝛽 (with 𝛽 depending on 𝛼, 𝛿) is possible. The influence of sets of half
the variables is of special interest:
Question 2.2. Given 𝜇( 𝑓 ) = 𝑜(1) what can be said about the maximum of the 𝐽𝑆+ ( 𝑓 )’s for
|𝑆| = 𝑛/2? What is the smallest 𝑡 such that for each 𝑓 with 𝜇( 𝑓 ) = 𝑡 there is some 𝑆 of size 𝑛/2
with 𝐽𝑆+ ( 𝑓 ) ≥ 1/2? (Here we assume that 𝑛 is even.)
3 Boolean functions without influential coalitions
In each construction we consider, for suitable 𝑘 and 𝑚, 𝑓 = 𝑚 𝑖=1 𝐶 𝑖 , where the 𝐶 𝑖 are random
Ó
disjunctions of 𝑘 literals using 𝑘 distinct variables (henceforth “𝑘-clauses”) and show that 𝑓 is
likely to have the desired properties. Every 𝐶 𝑖 can be regarded as a list of specifications for the
values of 𝑘 variables. We use 𝑔 𝑖 for the specification associated with 𝐶 𝑖 , and write 𝐶 𝑖 ∼ 𝑥 if
some entry of 𝑥 agrees with 𝑔 𝑖 . We say 𝐶 𝑖 misses 𝑆 ⊆ [𝑛] if the indices of all variables in 𝐶 𝑖 lie in
[𝑛] \ 𝑆.
Let 𝑠 = (1/2 − 𝛿)𝑛. We will always use 𝑆 for an 𝑠-subset of [𝑛] and (for such an 𝑆) set
𝑚𝑆 = |{𝑖 : 𝐶 𝑖 misses 𝑆}|. (Following common practice we omit irrelevant floor and ceiling
symbols, pretending all large numbers are integers. As in the case of 𝑘, 𝑚 and 𝑠, parameters not
declared to be constants are assumed to be functions of 𝑛.) We use log for log2 .
Both constructions will make use of the next two observations, with Theorem 1.1 following
immediately from these and Theorem 1.2 requiring a little more work.
√
Lemma 3.1. If 𝑘 = 𝑜( 𝑛) and (1/2 + 𝛿) 𝑘 𝑚 = 𝜔(𝑛) then w. h. p.
𝑚𝑆 ∼ (1/2 + 𝛿) 𝑘 𝑚 for all 𝑆 ∈ [𝑛]
𝑠 . (3.1)
(where, as usual, 𝑎 𝑛 ∼ 𝑏 𝑛 means 𝑎 𝑛 /𝑏 𝑛 → 1 and with high probability (w. h. p.) means with
probability tending to 1, both as 𝑛 → ∞).
𝑛−𝑠 𝑛 𝑘
√ 𝑆, 𝑚𝑆 has the binomial distribution 𝐵(𝑚, 𝑝), with 𝑝 = 𝑘 / 𝑘 ∼∗ (1/2 + 𝛿)
Proof. For a given
(using 𝑘 = 𝑜( 𝑛) for the “∼”). Thus 𝔼𝑚𝑆 = 𝑚𝑝 and, by “Chernoff’s Inequality” (e. g., [10,
Theorem 2.1]),
Pr(𝑚𝑆 ∉ ((1 − 𝜁)𝑚𝑝, (1 + 𝜁)𝑚𝑝)) < exp[−Ω(𝜁 2 𝑚𝑝)], (3.2)
for 𝜁 ∈ (0, 1). Applying this with a 𝜁 which is both 𝜔( 𝑛/(𝑚𝑝)) and 𝑜(1) gives Pr(𝑚𝑆 / 𝑚𝑝) <
p
2−𝜔(𝑛) , and the union bound then gives (3.1).
The next lemma is stated to cover both applications, though nothing so precise is needed for
Theorem 1.1.
∗ Though now commonly called a “Chernoff bound," this and related inequalities essentially go back to Sergei
Natanovich Bernstein in the early part of the 20th century; see [18].
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 6
I NFLUENTIAL C OALITIONS FOR B OOLEAN F UNCTIONS I: C ONSTRUCTIONS
Lemma 3.2. If there is a 𝜉 for which
exp[−𝜉2 𝑛] = 𝑜((1 − 2−𝑘 )𝑚 ) (3.3)
and
[(1 + 2𝜉)/4] 𝑘 = 𝑜(1/𝑚), (3.4)
then w. h. p.
𝜇( 𝑓 ) ∼ (1 − 2−𝑘 )𝑚 . (3.5)
Proof. This is a simple second moment method calculation (similar to what is done in [1], though
described differently there).
Recalling that 𝑥, 𝑦 always denote elements of {0, 1} 𝑛 , write 𝐴 𝑥 for the event { 𝑓 (𝑥) = 1} and
1𝑥 for its indicator, and set 𝑋 = 1𝑥 = 2𝑛 𝜇( 𝑓 ). Then Pr(𝐴 𝑥 ) = (1 − 2−𝑘 )𝑚 and 𝔼𝑋 = (1 − 2−𝑘 )𝑚 2𝑛 ;
Í
so we just need to show 𝔼𝑋 2 ∼ 𝔼2 𝑋 (equivalently, 𝔼𝑋 2 < (1 + 𝑜(1))𝔼2 𝑋), since Chebyshev’s
Inequality then gives Pr(|𝑋 − 𝔼𝑋 | > 𝜁𝔼𝑋) = 𝑜(1) for any fixed 𝜁 > 0.
We have ÕÕ Õ Õ
𝔼𝑋 2 = 𝔼1𝑥 1 𝑦 = Pr(𝐴 𝑥 ) Pr(𝐴 𝑦 |𝐴 𝑥 ),
𝑥 𝑦 𝑥 𝑦
so will be done if we show that for a fixed 𝑥,
Õ
Pr(𝐴 𝑦 |𝐴 𝑥 ) < (1 + 𝑜(1))(1 − 2−𝑘 )𝑚 2𝑛 .
𝑦
Since the sum is the same for all 𝑥, it is enough to prove this when 𝑥 = 0. Set 𝑍 = {𝑦 : |𝑦| <
(1/2 − 𝜉)𝑛} and recall that by Chernoff’s Inequality (3.2), |𝑍| < exp[−2𝜉2 𝑛]2𝑛 . It is thus enough
to show that (for 𝑥 = 0)
𝑦 ∉ 𝑍 ⇒ Pr(𝐴 𝑦 |𝐴 𝑥 ) < (1 + 𝑜(1))(1 − 2−𝑘 )𝑚 , (3.6)
since then, using (3.3), we have
Õ Õ
Pr(𝐴 𝑦 |𝐴 𝑥 ) < |𝑍| + Pr(𝐴 𝑦 |𝐴 𝑥 ) < (1 + 𝑜(1))(1 − 2−𝑘 )𝑚 2𝑛 .
𝑦 𝑦∉𝑍
Now since 𝑥 = 0, we have 𝐴 𝑥 = {𝑔 𝑖 ≠ 1 for all 𝑖}; so if, for a given 𝑦 ∉ 𝑍, we set
𝛽 = 𝛽 𝑦 = Pr(𝐶 𝑖 ∼ 𝑦|𝑔 𝑖 ≠ 1) (a function of |𝑦|), then Pr(𝐴 𝑦 |𝐴 𝑥 ) = 𝛽 𝑚 . Aiming for a bound on 𝛽,
we have
1 − 2−𝑘 = Pr(𝐶 𝑖 ∼ 𝑦)
= Pr(𝑔 𝑖 = 1) Pr(𝐶 𝑖 ∼ 𝑦|𝑔 𝑖 = 1) + Pr(𝑔 𝑖 ≠ 1) Pr(𝐶 𝑖 ∼ 𝑦|𝑔 𝑖 ≠ 1)
= 2−𝑘 Pr(𝐶 𝑖 ∼ 𝑦|𝑔 𝑖 = 1) + (1 − 2−𝑘 )𝛽
and
Pr(𝐶 𝑖 ∼ 𝑦|𝑔 𝑖 = 1) > 1 − (1 − |𝑦|/𝑛) 𝑘 ≥ 1 − (1/2 + 𝜉) 𝑘 =: 1 − 𝜈
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 7
J EAN B OURGAIN , J EFF K AHN , AND G IL K ALAI
(using the fact that if 𝑔 𝑖 = 1, then 𝑔 𝑖 / 𝑦 iff all indices of variables in 𝐶 𝑖 belong to {𝑗 : 𝑦 𝑗 = 0}).
Combining, we have
h −𝑘 −𝑘
i
(𝜈−2 )
𝛽 < (1 − 2−𝑘 )−1 [1 − 2−𝑘 − 2−𝑘 (1 − 𝜈)] = (1 − 2−𝑘 ) 1 + 2 (1−2−𝑘 )2 ,
which with (3.4) gives 𝛽 𝑚 < (1 + 𝑜(1))(1 − 2−𝑘 )𝑚 (which is (3.6)).
Proof of Theorem 1.1. Notice that it is enough to prove this with 𝜇( 𝑓 ) ∼ 𝛼 (rather than “= 𝛼”); for
then, since 𝑓 −1 (1) ⊆ 𝑔 −1 (1) trivially implies 𝐽𝑆+ ( 𝑓 ) ≤ 𝐽𝑆+ (𝑔) for all 𝑆, we can choose 𝛽 ∈ (𝛼, 1) and
a 𝑔 with 𝔼(𝑔) ∼ 𝛽 possessing the desired small influences, and shrink 𝑔 −1 (1) to produce 𝑓 .
Let 𝑘 = 𝐶 log 𝑛, with 𝐶 = 𝐶 𝛿 chosen so that (1 + 2𝛿) 𝑘 = 𝜔(𝑛) (e. g., 𝐶 = 1/𝛿 does this), and
𝑚 = 2 𝑘 ln(1/𝛼) = 𝑛 𝐶 ln(1/𝛼). Here all we use from Lemma 3.1 (whose hypotheses are satisfied
for our choice of 𝑘 and 𝑚) is the fact that w. h. p. 𝑚𝑆 ≠ 0 for all 𝑆, whence each 𝐽𝑆+ ( 𝑓 ) is at most
1 − 2−𝑘 = 1 − 𝑛 −𝐶 . On the other hand, by Lemma 3.2 (with, for example, 𝜉 = 0.1), we have
𝜇( 𝑓 ) ∼ 𝛼 w. h. p. So w. h. p. 𝑓 meets our requirements.
Proof of Theorem 1.2. . Here, intending to recycle 𝑛, 𝑚 and 𝑓 , we rename these quantities n, m
and f. We may of course assume 𝛿 is fairly small. Let (for example) 𝜉 = 𝛿/3, fix 𝜀 with 0 < 𝜀 < 𝜉2 ,
and set 𝑘 = (1 + 𝛿) log n and m = 𝜀2 𝑘 n. These values are easily seen to give the hypotheses of
Lemmas 3.1 and 3.2. In particular, we can say that w. h. p. the supports of the 𝐶 𝑖 are chosen so
(3.1) holds (note this says nothing about the values specified by the 𝑔 𝑖 ) and
𝔼(f) ∼ (1 − 2−𝑘 )m ∼ e−𝜀n . (3.7)
[n]
Set 𝑛 = (1/2 + 𝛿)n. Fix 𝑆 ∈ 𝑠 , set 𝑚 = 𝑚𝑆 , and let 𝑓 = 𝑓𝑆 be the conjunction of the 𝑚
clauses 𝐶 𝑖 —w.l.o.g. 𝐶1 , , . . . , , 𝐶 𝑚 —that miss 𝑆. Thus 𝑓 is the conjunction of 𝑚 ∼ (1/2 + 𝛿) 𝑘 m =
𝜀(1 + 2𝛿) 𝑘 n random 𝑘-clauses from a universe of 𝑛 variables. Theorem 1.2 (with 𝛼 = 𝛿) thus
follows from
Claim A. Pr(𝜇( 𝑓 ) > exp[−𝑛 𝛿 ]) < 𝑜(2−n )
(since then w. h. p. we have 𝔼( 𝑓𝑆 ) ≤ exp[−𝑛 𝛿 ] for every 𝑆).
Remarks. The actual bound in Claim A will be exp[−Ω(𝑚)], so much smaller than 2−n . Note that
here it does not matter whether we take 𝜇 to be our original measure (i. e., 𝜇 uniform on {0, 1}n )
or uniform measure on 𝑄 := {0, 1} 𝑛 ; but it is now more natural to think of the latter—and we
will do so in what follows—since our original universe plays no further role in this discussion.
It may also be worth noting that, unlike in the proof of Lemma 3.2, the second moment method
is not strong enough to give the exponential bound in Claim A.
Claim B. If 𝑋 ⊆ 𝑄, 𝜇(𝑋) = 𝛽 > exp[−𝑜(𝑛/log2 𝑛)] and 𝜁 = 𝑜(2−𝑘 ), then for a random 𝑘-clause 𝐶,
Pr(𝜇(𝐶 ∧ 𝑋) > (1 − 𝜁)𝜇(𝑋)) < 1/2
(where 𝐶 ∧ 𝑋 = {𝑥 ∈ 𝑋 : 𝐶 ∼ 𝑥}).
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 8
I NFLUENTIAL C OALITIONS FOR B OOLEAN F UNCTIONS I: C ONSTRUCTIONS
Remark. This is probably true for 𝛽 greater than something like exp[−𝑛/𝑘]. The bound in the
claim is just what the proof gives, and is more than enough for us since we are really interested
in much larger 𝛽.
Ó𝑗
To see that Claim B implies Claim A, set 𝑓 𝑗 = 𝑖=1 𝐶 𝑖 and notice that 𝜇( 𝑓 ) ≥ 𝛽 implies (for
example) n o
𝑖 : 𝔼( 𝑓𝑖 ) < 1 − 𝑚 𝔼( 𝑓𝑖−1 ) < 𝑚/5
5 ln(1/𝛽)
(3.8)
(and, of course, 𝔼( 𝑓𝑖 ) ≥ 𝛽 for all 𝑖). But if we take 𝛽 = exp[−𝑛 𝛿 ] then our choice of parameters
gives
𝜁 := 5𝑚 −1 ln(1/𝛽) = 𝑜(2−𝑘 )
(using 𝑚/ln(1/𝛽) = Θ(𝑛 (1+𝛿) log(1+2𝛿)+1−𝛿 ) and 2 𝑘 = 𝑛 1+𝛿 ), so Claim B bounds the probability of
(3.8) by
𝑚 −4𝑚/5
𝑚/5 2 = 𝑜(2−n ).
Proof of Claim B. Let 𝐺 be the bipartite graph on 𝑄 ∪ 𝑊, where 𝑊 is the set of (𝑛 − 𝑘)-dimensional
subcubes of 𝑄 and, for (𝑥, 𝐷) ∈ 𝑄 ×𝑊, we take 𝑥 ∼ 𝐷 if 𝑥 ∈ 𝐷. (So we have gone to complements:
for a clause 𝐶 the corresponding subcube is 𝐷 = {𝑦 : 𝐶 / 𝑦}, so 𝐶 ∧ 𝑋 = 𝑋 \ 𝐷.)
Assuming Claim B fails at 𝑋, fix 𝑇 ⊆ 𝑊 with |𝑇 | = |𝑊 |/2 and
𝐷 ∈ 𝑇 ⇒ 𝜇(𝐷 ∩ 𝑋) < 𝜁𝜇(𝑋),
and set 𝑅 = 𝑊 \ 𝑇.
Consider the experiment: (i) choose 𝑥 uniformly from 𝑋; (ii) choose 𝐷 uniformly from the
members of 𝑊 containing 𝑥; (iii) choose 𝑦 uniformly from 𝐷.
Claim C. Pr(𝑦 ∈ 𝑋) > (2 − 𝑜(1))𝛽.
Proof. Since each triple (𝑥, 𝐷, 𝑦) with 𝑥 ∈ 𝑋 and 𝑥, 𝑦 ∈ 𝐷 is produced by (i)-(iii) with probability
|𝑋 | −1 · 2 𝑘 |𝑊 | −1 · 2 𝑘−𝑛 , we just need to show that the number of such triples with 𝑦 ∈ 𝑋 is at least
(2 − 𝑜(1))𝛽|𝑋 ||𝑊 |2𝑛 2−2𝑘 = (2 − 𝑜(1))|𝑋 | 2 |𝑊 |2−2𝑘 .
Writing 𝑑 for degree in 𝐺, we have
Õ Õ
𝑑𝑇 (𝑥) = 𝑑𝑋 (𝐷) < |𝑇 |𝜁|𝑋 |,
𝑥∈𝑋 𝐷∈𝑇
implying
Õ Õ
𝑑𝑋 (𝐷) = (𝑑(𝑥) − 𝑑𝑇 (𝑥))
𝐷∈𝑅 𝑥∈𝑋
> |𝑋 ||𝑊 |2−𝑘 − 𝜁|𝑇 ||𝑋 | = (1 − 𝑜(1))|𝑋 ||𝑊 |2−𝑘 .
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 9
J EAN B OURGAIN , J EFF K AHN , AND G IL K ALAI
The number of triples (𝑥, 𝐷, 𝑦) as above is thus
!2
Õ Õ Õ
𝑑𝑋
2
(𝐷) ≥ 𝑑𝑋
2
(𝐷) ≥ 𝑑𝑋 (𝐷) /|𝑅|
𝐷∈𝑊 𝐷∈𝑅 𝐷∈𝑅
> (1 − 𝑜(1))|𝑋 | |𝑊 | |𝑅| −1 2−2𝑘 = (2 − 𝑜(1))|𝑋 | 2 |𝑊 |2−2𝑘 .
2 2
Let 𝑇(𝑥) be the random element of 𝑄 obtained from 𝑥 by choosing 𝐾 uniformly from [𝑛]
𝑘
and randomly (uniformly, independently) resampling the 𝑥 𝑖 for 𝑖 ∉ 𝐾. Then 𝑦 obtained from
𝑥 by (ii) and (iii) above is just 𝑇(𝑥), so the next assertion contradicts Claim C, completing the
proof of Claim B (and Theorem 1.2).
Claim D. If 𝜇(𝑋) > exp[−𝑜(𝑛/log2 𝑛)] and 𝑥 is uniform from 𝑋, then Pr(𝑇(𝑥) ∈ 𝑋) < (1+𝑜(1))𝜇(𝑋).
Remark. If 𝑋 is a subcube of codimension 𝑛/𝑘, say 𝑋 = {𝑥 : 𝑥 ≡ 0 on 𝐿} with |𝐿| = 𝑛/𝑘, then for
any 𝑥 ∈ 𝑋,
Õ Õ
Pr(𝑇(𝑥) ∈ 𝑋) = Pr(|𝐾 ∩ 𝐿| = 𝑡)2−(|𝐿|−𝑡) = 𝜇(𝑋) Pr(|𝐾 ∩ 𝐿| = 𝑡)2𝑡 ,
𝑡 𝑡
and, since |𝐾 ∩ 𝐿| is essentially Poisson with mean 1, the sum is approximately e−1 𝑡 2𝑡 /𝑡! = e.
Í
So Claim D fails for 𝜇(𝑋) = 2−𝑛/𝑘 and, as earlier, it is natural to guess that it holds if 𝜇(𝑋) is
much greater than this.
Proof of Claim D. Let 𝑄 𝑟 = {𝑦 ∈ 𝑄 : |𝑦| ≤ 𝑟}. The assumption on 𝜇(𝑋) implies that 𝜇(𝑄 𝑟−1 ) <
𝜇(𝑋) ≤ 𝜇(𝑄 𝑟 ) for some 𝑟 > (1/2 − 𝑜(1/𝑘))𝑛, so Claim D follows from
Claim E. If 𝜑 = 𝑜(1/𝑘) and 𝑟 > (1/2 − 𝜑)𝑛, then for any 𝑥 ∈ 𝑄 and 𝑋 ⊆ 𝑄 with
𝜇(𝑋) ≤ 𝜇(𝑄 𝑟 ), (3.9)
we have
Pr(𝑇(𝑥) ∈ 𝑋) < (1 + 𝑜(1))𝜇(𝑄 𝑟 ). (3.10)
Proof. We may assume 𝑥 = 0, so that Pr(𝑇(𝑥) = 𝑦) is a decreasing function of |𝑦|. We thus
maximize Pr(𝑇(𝑥) ∈ 𝑋) subject to (3.9) by taking 𝑋 = 𝑄 𝑟 , and (3.10) is then a routine calculation
using
𝜇(𝑋) = Pr(Bin(𝑛, 1/2) ≤ 𝑟)
and
Pr(𝑇(𝑥) ∈ 𝑋) = Pr(Bin(𝑛 − 𝑘, 1/2) ≤ 𝑟)
(where Bin(·, ·) denotes a binomially distributed r.v.).
Acknowledgment We would like to thank Roy Meshulam for helpful conversations. Part of this
work was carried out while the second author was visiting Jerusalem under BSF grant 2006066.
The first author thanks the UC Berkeley Mathematics Department for its hospitality.
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 10
I NFLUENTIAL C OALITIONS FOR B OOLEAN F UNCTIONS I: C ONSTRUCTIONS
References
[1] Miklós Ajtai and Nathan Linial: The influence of large coalitions. Combinatorica, 13(2):129–
145, 1993. [doi:10.1007/BF01303199] 3, 7
[2] Noga Alon, Guy Moshkovitz, and Noam Solomon: Traces of hypergraphs. J. London Math.
Soc., 100(2):498–517, 2019. [doi:10.1112/jlms.12233] 5
[3] Michael Ben-Or and Nathan Linial: Collective coin flipping. In Silvio Micali, editor,
Randomness and Computation, volume 5 of Advances in Computing Research, pp. 91–115. JAI
Press, 1989. DSpace@MIT. Preliminary version in FOCS’85. 2, 4
[4] Béla Bollobás and Andrew J Radcliffe: Defect Sauer results. J. Combin. Theory–A,
72(2):189–208, 1995. [doi:10.1016/0097-3165(95)90060-8] 5
[5] John Adrian Bondy: Induced subsets. J. Combin. Theory–B, 12(2):201–202, 1972.
[doi:10.1016/0095-8956(72)90025-1] 5
[6] Jean Bourgain, Jeff Kahn, and Gil Kalai: Influential coalitions for Boolean functions, 2014.
[arXiv:1409.3033] 3
[7] Benny Chor: Private communication, circa 1990. 2
[8] Péter Frankl: On the trace of finite sets. J. Combin. Theory–A, 34(1):41–45, 1983.
[doi:10.1016/0097-3165(83)90038-9] 5
[9] Sergiu Hart: A note on the edges of the 𝑛-cube. Discr. Math., 14(2):157–163, 1976.
[doi:10.1016/0012-365X(76)90058-3] 3
[10] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński: Random Graphs. Wiley, 2000.
[doi:10.1002/9781118032718] 6
[11] Jeff Kahn and Gil Kalai: Thresholds and expectation thresholds. Combin. Probab. Comput.,
16(3):495–502, 2007. [doi:10.1017/S0963548307008474] 3
[12] Jeff Kahn, Gil Kalai, and Nathan Linial: The influence of variables on Boolean functions.
In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc., 1988. [doi:10.1109/SFCS.1988.21923] 2, 3, 4
[13] Gil Kalai: Nati’s influence. Combinatorics and More, Gil Kalai’s blog, May 2008. LINK. 2
[14] Nathan Linial: Open problem. In Jeff Kahn, Angelika Steger, and Benny Sudakov,
editors, Oberwolfach Report No. 01/2011, pp. 75–76. 2011. LINK. 2
[15] Norbert Sauer: On the density of families of sets. J. Combin. Theory–A, 13(1):145–147, 1972.
[doi:10.1016/0097-3165(72)90019-2] 5
[16] Saharon Shelah: A combinatorial problem; stability and order for models and theories in
infinitary languages. Pacific J. Math, 41(1):247–261, 1972. Project Euclid. 5
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 11
J EAN B OURGAIN , J EFF K AHN , AND G IL K ALAI
[17] Vladimir N. Vapnik and Alexei Ya. Chervonenkis: On the uniform convergence of relative
frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–
280, 1971. Reproduced in Measure of Complexity: Festschrift for Alexei Chervonenkis,
Springer 2015. [doi:10.1137/1116025] 5
[18] Wikipedia: Bernstein inequalities (probability theory). Accessed 06-09-2024. 6
AUTHORS
Jean Bourgain
Past Professor
Department of Mathematics
Institute for Advanced Study
Princeton NJ 08540
https://www.ias.edu/scholars/bourgain
Jeff Kahn
Professor
Department of Mathematics
Rutgers University
Piscataway NJ 08854
jkahn math rutgers edu
https://sites.math.rutgers.edu/~jkahn/
Gil Kalai
Professor
Einstein Institute of Mathematics
Hebrew University of Jerusalem
Jerusalem, Israel
and
Efi Arazi School of Computer Science
Reichman University, Herzliya.
kalai math huji ac il
http://www.ma.huji.ac.il/~kalai/
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 12
I NFLUENTIAL C OALITIONS FOR B OOLEAN F UNCTIONS I: C ONSTRUCTIONS
ABOUT THE AUTHORS
Jean Bourgain (1954–2018) received his Ph. D. from the Vrije Universiteit Brussel in
1977. He was professor at I.H.E.S., the University of Illinois, and from 1994, at
the Institute for Advanced Study in Princeton. He worked on functional analysis,
harmonic analysis, ergodic theory, partial differential equations, number theory,
and combinatorics. He was a recipient of the Fields Medal (1994), the Shaw Prize
(2010), and the Breakthrough Prize (2017).
Jeff Kahn received his Ph. D. from The Ohio State University in 1979, under the
direction of D. K. Ray-Chaudhuri, and, following some time at MIT, has been at
Rutgers since 1984. He works on discrete mathematics and related topics, and is
a recipient of the Pólya Prize (1996) and the Fulkerson Prize (2012).
Gil Kalai graduated from the Hebrew University of Jerusalem in 1983; his advisor
was Micha A. Perles. He works on geometric and probabilistic combinatorics,
convexity, and linear programming. He is known for his blog, his interest in
advancing women in academia, and his “argument against quantum computers."
T HEORY OF C OMPUTING, Volume 20 (4), 2024, pp. 1–13 13