Boolean functions: noise stability, non-interactive
correlation, and mutual information
Jiange Li, Muriel Médard

arXiv:1801.04462v1 [math.PR] 13 Jan 2018

Research Laboratory of Electronics
Massachusetts Institute of Technology
Cambridge, MA 02139, USA
Email: lijiange, medard@mit.edu

Abstract—Let ǫ ∈ [0, 1/2] be the noise parameter and p > 1.
We study the isoperimetric problem that for fixed mean Ef which
Boolean function f maximizes the p-th moment E(Tǫ f )p of the
noise operator Tǫ acting on Boolean functions f : {0, 1}n 7→
{0, 1}. Our findings are: in the low noise scenario, i.e., ǫ is small,
the maximum is achieved by the lexicographical function; in the
high noise scenario, i.e., ǫ is close to 1/2, the maximum is achieved
by Boolean functions with the maximal degree-1 Fourier weight;
and when p is a large integer, the maximum is achieved by
some monotone function, which particularly implies that, among
balanced Boolean functions, the maximum is achieved by any
function which is 0 on all strings with fewer than n/2 1’s.
Our results recover Mossel and O’Donnell’s results about the
problem of non-interactive correlation distillation, and confirm
Courtade and Kumar’s Conjecture on the most informative
Boolean function in the low noise and high noise regimes. We also
observe that Courtade and Kumar’s Conjecture is equivalent to
that the dictator function maximizes E(Tǫ f )p for p close to 1.
Index Terms—Boolean function; noise stability; non-interactive
correlation; the most informative Boolean function.

I. I NTRODUCTION
Let Tǫ be the noise operator (the definition will be given
in Section 2) acting on Boolean functions defined on the
discrete cube {0, 1}n associated with the uniform measure. We
are interested in the problem that given the mean Ef which
Boolean function f maximizes the p-th moment E(Tǫ f )p
for p ≥ 1. The second moment, i.e., p = 2, is known as
nose stability of f , and the study of noise stability plays an
important role in many areas of mathematics and computer
sciences, such as inapproximability [7], learning theory [1],
[11], hardness amplification [15], mixing of short random
walks [9], and percolation [2]. We may refer to E(Tǫ f )p as
p-stability of the Boolean function f . In the Gaussian setting,
Borell’s isoperimetric inequality [3] for two functions asserts
that half spaces are the extremizers, and this is generalized by
Isaksson and Mossel [8] to multiple functions. The general pstability in the Gaussian setting is studied by Eldan [5]. In the
discrete setting, we still lack the knowledge of the extremizers.
The problem of noise stability is closely related to the
problem of non-interactive correlation distillation (NICD) [13],
[14], [18], which is relevant for cryptographic information
reconciliation, random beacons in cryptography and security,
and coding theory. In its most basic form, the problem of
NICD involves two players. Let X ∈ {0, 1}n be a uniformly
random binary string transmitted to Alice and Bob through

independent binary symmetric channels BSC(ǫ) with cross
error probability ǫ, i.e., each bit of X is flipped independently with probability ǫ. Alice and Bob receive Y and Y ′ ,
respectively. They wish to maximize the agreement probability
P(f (Y ) = g(Y ′ )) using Boolean functions f and g, respectively. Notice that
Ef (Y ) = P(f (Y ) = g(Y ′ ) = 1) + P(f (Y ) = 1, g(Y ′ ) = 0),
Eg(Y ′ ) = P(f (Y ) = g(Y ′ ) = 1) + P(f (Y ) = 0, g(Y ′ ) = 1).
We have
P(f (Y ) = g(Y ′ )) = 1 + 2Ef (Y )g(Y ′ ) − Ef (Y ) − Eg(Y ′ ).
Given Ef and Eg, it suffices to maximize the correlation
Ef (Y )g(Y ′ ) = E(Tǫ f Tǫ g). The goal of the k-player NICD
problem is to maximize P(f1 (Y 1 ) = · · · = fk (Y k )),
where Y 1 , · · · , Y k are k noise corrupted versions of X, and
f1 , · · · , fk are Boolean functions. In general, there is no
equivalence of the NICD
the problem of the
Q problem and Q
maximal correlation E ki=1 fi (Y i ) = E ki=1 Tǫ fi . We will
show that, if the maximal correlation is achieved by certain
type of Boolean functions, then the agreement probability is
also maximized by the same type of Boolean functions.
Let X and Y be random binary strings defined as before,
and let f be a Boolean function. Courtade and Kumar [4]
conjectured that the mutual information between X and f (Y )
is maximized by the dictator function. Its Gaussian analogy
has recently been solved by Kindler, O’Donnell and Witmer
[12]. Pichler, Piantanida and Matz [16] proved the variant
that the dictator function maximizes the mutual information
between f (X) and g(Y ) among all Boolean functions f
and g. The original conjecture is only verified in the high
noise regime, i.e., ǫ close to 1/2, by Samorodnitsky [17].
Our observation is that Courtade and Kumar’s Conjecture
is equivalent to that the dictator function maximizes the pstability E(Tǫ f )p for p close to 1. This may provide a different
perspective to attack the original conjecture.
The paper is organized as follows. In Section II, we introduce the noise operator as well as some of its properties. In
Section III, we include results in different scenarios, such as
the low noise (i.e., ǫ is small) and the high noise (i.e., ǫ is
close to 1/2), as well as the asymptotic result when p is a
large integer. We conclude this paper with the discussion of

the connection between noise stability and the problem of the
most informative Boolean function in Section IV.
II. N OISE OPERATOR
Any real-valued function f defined on the discrete cube
{0, 1}n associated with the uniform measure µ has the following Fourier expansion
X
fˆ(A)WA (x),
f (x) =
A⊆[n]

whereP fˆ(A) are Fourier coefficients of f , and {WA (x) =
(−1) i∈A xi : A ⊆ [n]} is the orthonormal basis, i.e.
E(WA )2 = 1 and E(WA WB ) = 0 for A 6= B. Particularly,
we have fˆ(∅) = Ef .
Definition 2.1: Let 0 ≤ ǫ ≤ 1/2. The noise operator Tǫ
acting on f : {0, 1}n 7→ R is defined as
X
(1 − 2ǫ)|A| fˆ(A)WA (x).
(Tǫ f )(x) =
A⊆[n]

We have the following probabilistic interpretation for the noise
operator. Let X ∈ {0, 1}n be a uniform binary string, and let
Y be the output of X through BSC(ǫ), i.e., Y = X +Z, where
the coordinates of Z are i.i.d. Bernoulli(ǫ). Then we have
(Tǫ f )(x) = E[f (Y )|X = x] = Ef (x + Z),

(1)

which follows from elementary calculations using the Fourier
representation. As a consequence, the operator Tǫ preserves
the mean, i.e., E(Tǫ f ) = Ef , which also easily follows from
the definition. We can also think of Tǫ as a Markov diffusion
operator. Think f as a vector with 2n coordinates. We have
(Tǫ f )(x) = (M f )(x),
where M is the transition matrix with M (x, y) = ǫd(x,y) (1 −
ǫ)n−d(x,y) and d(·, ·) is the Hamming distance. The transition
matrix M is invertible if ǫ 6= 0 or 1/2.
Let Y 1 , · · · , Y k be independent copies of Y defined as
before. They can be realized as Y i = X + Z i , where Z i
are independent copies of Z. Each pair (Y i , Y j ) for i 6= j has
correlation matrix ρI, where ρ = (1−2ǫ)2, and I is the identity
matrix. For simplicity, we say that they are ρ-correlated. Notice
that Yi are independent given the information of X. Using the
conditioning argument with (1), we have
E

k
Y

fi (Y i ) = E

k
Y

Tǫ fi .

i=1

i=1

Owing to this relation, the results in the next section will be
stated in terms of either LHS or RHS of the identity above.
The following property of Tǫ will be needed in Section
III. Let ϕ be a convex function. Then Eϕ(Tǫ f ) is a decreasing function of ǫ. We redefine the noise operator as
Pt = T(1−e−t )/2 for t ≥ 0, since {Pt , t ≥ 0} forms an
additive Markov semi-group, i.e., Pt1 ◦ Pt2 = Pt1 +t2 , with
the infinitesimal generator L defined as
X
|A|fˆ(A)WA (x).
(2)
(Lf )(x) = −
A⊆[n]

Differentiating the equation E(Pt f ) = Ef with respect to t
at t = 0, we have E(Lf ) = 0 for any function f . Jensen’s
inequality implies that Pt (ϕ(f )) ≥ ϕ(Pt f ). Differentiating
this inequality with respect to t at t = 0, we have L(ϕ(f )) ≥
ϕ′ (f )Lf . Then the desired monotone property follows from
d
Eϕ(Pt f ) = Eϕ′ (Pt f )L(Pt f ) ≤ EL(ϕ(Pt f )) = 0.
dt
An important notation used in the study of Boolean functions is the total influence. Let σi be the flipping operator
defined as σi (x1 , · · · , xi , · · · , xn ) = (x1 , · · · , 1−xi , · · · , xn ).
Definition 2.2: Let f : {0, 1}n 7→ {0, 1} be a Boolean
function. The influence of the i-th variable is defined as
Ii (f ) = µ(x : f (x) 6= f (σi (x))).
Pn
The total influence is defined as I(f ) = i=1 Ii (f ). Using
P
Fourier expansion, we have I(f ) = 4 A⊆[n] |A|fˆ(A)2 .
The following are some typical Boolean functions needed
in Section III.
Definition 2.3: A lexicographical set is a set with elements
selected in the lexicographical order. A Boolean function f is
called lexicographical if it is supported on a lexicographical
set.
Definition 2.4: The majority functionPof n (odd number)
n
variables is defined as Majn (x) = sgn ( i=1 xi − n/2). The
dictator function is Maj1 , which only looks at the first bit.
Definition 2.5: The natural partial order relation on {0, 1}n
is defined as x  y if xi ≤ yi holds for all i ∈ [n]. We say
that f is monotone if f (x) ≤ f (y), whenever x  y.
III. M AIN

RESULTS

For the problem of k-player correlation, the following
statement asserts that the players should use the same strategy
to maximize their correlation.
Proposition 3.1: Let 0 < ρ < 1. Let Y 1 , · · · , Y k ∈ {0, 1}n
be ρ-correlated uniform binary strings. For any functions fi :
{0, 1}n 7→ R, we have
E

k
Y

i=1

fi (Y i ) ≤ max E
1≤i≤k

n
Y

fi (Y j ).

j=1

Equality is achieved if and only if fi are multiples of the same
function.
Proof: As we have seen, we can realize Y i as X + Z i ,
where X is a uniform binary sequence, and the coordinates of
√
Z i are i.i.d. Bernoulli(ǫ) with ǫ = (1 − ρ)/2. Since Y i are
independent given X, we have
E

k
Y

fi (Y i ) = E

i=1

≤
=

k
Y

E[fi (Y i )|X]

i=1
k
Y

(E(E[fi (Y i )|X])k )1/k

i=1
k
Y

i=1



E

k
Y

j=1

1/k

E[fi (Y j )|X]

=

k
Y

i=1



E

1/k

j=1

≤ max E
1≤i≤k

k
Y

n
Y

Since O(·) term has mean zero, for ǫ close to 1/2, we have

fi (Y j )

n
X
d
fˆ({i})2
E(Tǫ f )p = −2p(p − 1)(1 − 2ǫ)(Ef )p−2
dǫ
i=1

fi (Y j ).

+ O((1 − 2ǫ)2 ).

j=1

The first inequality follows from Hölder’s inequality, and
equality is achieved if only if E[fi (Y i )|X] are multiples of
the same function. Since the noise operator is invertible, fi
should also be multiples of the same function.
Harper’s Theorem [6] asserts that the lexicographical set
has the least edge boundary among all subsets of {0, 1}n with
fixed size. This is equivalent to that the lexicographical function has the minimal total influence among Boolean functions
with fixed mean.
Theorem 3.1: Let p > 1, n and Ef be fixed. When ǫ is
sufficiently small, E(Tǫ f )p is maximized by the lexicographical function (given in Definition 2.3). When ǫ is sufficiently
close to 1/2, E(Tǫ f )p is maximized by Boolean
functions
P
with the maximal degree-1 Fourier weight ni=1 fˆ({i})2 . If
f is assumed to be balanced, i.e., P(f = 0) = P(f = 1), the
dictator function (given in Definition 2.4) maximizes E(Tǫ f )p
in both scenarios.
Proof: Differentiating E(Tǫ f )p with respect to ǫ, we have
d
E(Tǫ f )p = 2p(1 − 2ǫ)−1 E(Tǫ f )p−1 (L ◦ Tǫ )f,
dǫ
where the operator L is defined in (2). In particular, we have
d
E(Tǫ f )p
dǫ

ǫ=0

= 2pE(f p−1 Lf )
= 2pE(f Lf )
X
|A|fˆ(A)2
= −2p
A⊆[n]

= −pI(f )/2,

(3)

where I(f ) is the total influence of f (given in Definition
d
2.2). Harper’s Theorem [6] and (3) imply that dǫ
E(Tǫ f )p
ǫ=0
is maximized by the lexicographical function. For p > 1,
we know that E(Tǫ f )p is decreasing as a function of ǫ.
Since E(T0 f )p = Ef is fixed, the lexicographical function
maximizes E(Tǫ f )p for small ǫ ≥ 0. When ǫ is close to 1/2,
(Tǫ f )(x) = Ef + (1 − 2ǫ)

n
X
i=1

fˆ({i})(−1)xi + O((1 − 2ǫ)2 ),

where O(·) depends on n, k not f . Then we have
(Tǫ f )p−1 (x) = (p − 1)(Ef )p−2 (1 − 2ǫ)

n
X

fˆ({i})(−1)xi

i=1

+ (Ef )p−1 + O((1 − 2ǫ)2 ),
and
(L ◦ Tǫ )f (x) = −(1 − 2ǫ)

n
X
i=1

fˆ({i})(−1)xi + O((1 − 2ǫ)2 ).

Notice that E(T1/2 f )p = (Ef )p . When ǫ is sufficiently
p
close to 1/2,
PnE(Tˆǫ f ) is2 maximized by the function which
maximizes i=1 f ({i}) . If f is assumed to be balanced, it is
clear that lexicographical function is just the dictator function.
Notice that
n
X
X
fˆ(A)2 = Ef − (Ef )2
fˆ({i})2 ≤
i=1

A⊆[n]

and that equality holds if f is the dictator function.
Remark 3.1: Our arguments could yield explicit bounds of
the noise level ǫ, but they will depend on the dimension n. It
is reasonable to ask if one can make it dimension-free.
If E(Tǫ f )p is maximized by the lexicographical function,
it also achieves the maximum at the function supported on
a reverse lexicographical set. This implies that E(Tǫ f )p and
E(Tǫ (1 − f ))p are maximized by the same lexicographical
function. It is clear that f and 1 − f have the same degree-1
Fourier weight. As a consequence of Theorem 3.1, we have
the following result on the k-player NICD problem, which is
proved by Mossel and O’Donnell [13] for balanced Boolean
functions.
Corollary 3.1: Let 0 < ρ < 1. Let Y 1 , · · · , Y k ∈ {0, 1}n be
ρ-correlated uniform binary strings. If ρ is sufficiently small,
then the agreement probability P(f (Y 1 ) = · · · = f (Y k ))
is maximized by the Boolean
f with the maximal
Pn function
ˆ({i})2 . If ρ is close 1, the
degree-1 Fourier weight
f
i=1
agreement probability is maximized by the lexicographical
function.
In the strong correlation regime, i.e., ρ close to 1, we have
the following heuristic explanation for the two-player case.
Suppose that f is supported on S. Our goal is to maximize
P(Y 1 ∈ S, Y 2 ∈ S), which is equivalent to minimize
P(Y 1 ∈ S, Y 2 ∈
/ S). Since Y 1 and Y 2 are ρ-correlated,
we can think of Y 2 as obtained from Y 1 by flipping its
coordinates independently with probability (1 − ρ)/2. When
ρ is close to 1, it is more likely that Y 1 and Y 2 only differ
by one bit. Therefore, Y 2 escapes from S only if Y 1 is close
to the boundary ∂S. Then smaller boundary implies larger
agreement probability. Harper’s Theorem [6] asserts that the
lexicographical set has the least boundary among all sets with
fixed size.
The question of precisely maximizing the degree-1 Fourier
weight among Boolean functions with fixed mean is a wellknown difficult one. The following example shows that the
indicator of Hamming ball is superior to the lexicographical
function when the mean is sufficiently small. Suppose that
−m
Ef = 2Q
for 1 ≤ m ≤ n. The lexicographical function
m
f (x) = i=1 xi is supported on a sub-cube S. When |S| is
small, we can let the Boolean function g be supported on a
vertex and |S| − 1 vertices with Hamming distance 1 from

that vertex. Calculations will show that P(f (Y 1 ) = f (Y 2 )) is
smaller than P(g(Y 1 ) = g(Y 2 )) for small ρ > 0.
Among balanced functions, the dictator function maximizes
E(Tǫ f )2 at any noise level. This simply follows from
X
(1 − 2ǫ)2|A| fˆ(A)2
E(Tǫ f )2 =

be either the indicator function f (y) = y1 or the flipping function f (y) = 1 − yi . In either case, g is the indicator function.
Both sides in our claim are 0 if any determined function is
the constant function 0. So we assume that all determined
functions are 1. Among the un-determined functions, suppose
there are a indicator functions and b flipping functions. Then
we have
(5) = (ǫa (1 − ǫ)b + (1 − ǫ)a ǫb )/2,

where the upper bound is achieved by the dictator function.
Notice that for balanced functions

(6) = (ǫa+b + (1 − ǫ)a+b )/2.

A⊆[n]

≤ (Ef )2 + (1 − 2ǫ)2 (Ef − (Ef )2 ),

Then the claim (4) is equivalent to

a 
b
a+b

ǫ
ǫ
ǫ
+
≤1+
,
1−ǫ
1−ǫ
1−ǫ

Ef (Y 1 )f (Y 2 ) = E(1 − f (Y 1 ))(1 − f (Y 2 ))
Therefore, we have
P(f (Y 1 ) = f (Y 2 )) = 2Ef (Y 1 )f (Y 2 ),
which is maximized by the dictator function. Similarly, we
have
P(f (Y 1 ) = f (Y 2 ) = f (Y 3 )) = 3Ef (Y 1 )f (Y 2 ) − 1/2.
Therefore, the dictator function is still the best strategy in
the three-player case. This recovers Theorem 1.3 of Mossel
and O’Donnell [13]. However, we do not know if the dictator
function also maximizes the third moment E(Tǫ f )3 among
balanced Boolean functions.
Techniques in our proof of the following result are borrowed from Mossel and O’Donnell [13], which studies of the
maximal agreement probability P(f (Y 1 ) = · · · = f (Y k )) for
balanced Boolean functions.
Theorem 3.2: Let 0 < ρ < 1. Let Y 1 , · · · , Y k ∈ {0, 1}n
be ρ-correlatedQuniform binary strings. Given the mean Ef ,
k
the quantity E i=1 f (Y i ) is maximized by some monotone
function (given in Definition 2.5).
Proof: The proof is a combination of a shifting argument
due to Kleitman [10] and the conditioning argument. Let g
be a function obtained from f in the following way. For any
x ∈ {0, 1}n, we define g(x) = f (x) if f (x) = f (σ1 (x)), i.e.,
f (x) is determined by the last n − 1 bits of x; otherwise, we
define g(x) = x1 . It is easy to check that g has the same mean
as f . We claim that g is superior to f , i.e.,
E

k
Y

i=1

i

f (Y ) ≤ E

k
Y

g(Y i ).

(4)

i=1

1
k
It suffices to show that for any y2,n
, · · · , y2,n
∈ {0, 1}n−1,
#
" k
Y
i
i
i
f (Y )|Y2,n = y2,n , 1 ≤ i ≤ k
(5)
E
i=1

can not exceed
#
" k
Y
i
i
i
g(Y )|Y2,n = y2,n , 1 ≤ i ≤ k .
E

(6)

i=1

i
i
Conditioned on Y2,n
= y2,n
, f (Y i ) is a one-variable Boolean
i
function. If its value is determined by y2,n
, i.e. it is a constant
function 0 or 1, then we have g(y) = f (y). Otherwise, it could

which follows from the convexity of the function t ∈ R 7→

t
ǫ
. The equality is achieved if and only if a = 0
1−ǫ
or b = 0, i.e., f is anti-monotone (flipping function) or
monotone (indicator function) on the first coordinate. Repeat
the procedure for all other coordinates. We will arrive at a
monotone
Qk function.
If E i=1 f (Y i ) is maximized by some monotone function,
it should also achieveQthe maximum at Q
an anti-monotone
k
k
function. Therefore, E i=1 f (Y i ) and E i=1 (1 − f )(Y i )
can be maximized by the same monotone function. As a
consequence of Theorem 3.2, we have the following result on
the k-player NICD problem, which was obtained by Mossel
and O’Donnell [13] for balanced Boolean function.
Corollary 3.2: Let 0 < ρ < 1. Let Y 1 , · · · , Y k ∈ {0, 1}n be
ρ-correlated uniform binary strings. Given the mean Ef , the
agreement probability P(f (Y 1 ) = · · · = f (Y k )) is maximized
by some monotone function.
We have seen from Theorem 3.1 that among balanced
Boolean functions the dictator function maximizes E(Tǫ f )k
in both the low noise and the high noise scenarios for fixed
n and k. One may expect that the same property holds for
arbitrary noise. The following result asserts that this is not
true if k is large.
Theorem 3.3: Let n, ǫ be fixed and let k be sufficiently large.
Among balanced Boolean function, the quantity E(Tǫ f )k is
maximized by any function which is 0 on all strings with fewer
than n/2 1’s. In particular, for n odd, E(Tǫ f )k is maximized
by the majority function Majn (given in Definition 2.4).
The proof depends on the following observations due to
Mossel and O’Donnell [13].
Lemma 3.1: For monotone functions, (Tǫ f )(x) is maximized at x = ~1 = (1, · · · , 1).
Proof: Notice that flipping each bit of a string with
probability ǫ is equivalent to update each bit with probability
2ǫ, where the update consists of replacing the bit by a random
choice from {0, 1}. For any x ∈ {0, 1}n, we denote by x′
the noised version of x. We couple the random sequences
x′ and ~1′ in the following way: update the same bit of x
and ~1 with the same value. It is clear that x′  ~1′ . By
monotonicity, we have f (~1′ ) = 1 if f (x′ ) = 1. Therefore,
we have (Tǫ f )(x) ≤ (Tǫ f )(~1).

Lemma 3.2: Among balanced Boolean function, (Tǫ f )(~1) is
maximized by any function which is 0 on all strings with fewer
than n/2 1’s. In particular, for n odd, (Tǫ f )(~1) is maximized
by the majority function Majn .
Proof: The statement simply follows from
X
~
~
(Tǫ f )(~1) =
ǫd(x,1) (1 − ǫ)n−d(x,1) ,
x∈S

where S is the support of f , and d(x, ~1) is the Hamming
distance between x and ~1, and the simple fact that the quantity
being summed is strictly decreasing with respect to d(x, ~1).
Proof: (Theorem 3.3). We only prove the theorem for n
odd, since the proof for n even is essentially the same. Invoke
Theorem 3.2, then we can assume that f is monotone. Using
Lemma 3.1, we have
X
E(Tǫ f )k = 2−n
(Tǫ f (x))k ≤ ((Tǫ f )(~1))k .
x

It is clear that

X
E(Tǫ Majn )k = 2−n
((Tǫ Majn )(x))k ≥ 2−n ((Tǫ Majn )(~1))k .
x

By Lemma 3.2, if f 6= Majn , we have (Tǫ f )(~1) <
(Tǫ Majn )(~1). For sufficiently large k, we will have
(Tǫ f (~1))k < 2−n (Tǫ Majn (~1))k .
Then we can recover the following result of Mossel and
O’Donnell [13].
Corollary 3.3: Let 0 < ρ < 1. Let Y 1 , · · · , Y k ∈ {0, 1}n
be ρ-correlated uniform binary strings. For sufficiently large k,
among balanced Boolean functions, P(f (Y 1 ) = · · · = f (Y k ))
maximized by any function which is 0 on all strings with
fewer than n/2 1’s. For n odd, the agreement probability is
maximized by the majority function Majn .
IV. T HE MOST

INFORMATIVE

B OOLEAN

FUNCTION

n

Let X ∈ {0, 1} be a uniform binary string, and let Y
be the output of X through BSC(ǫ), i.e., Y = X + Z,
where the coordinates of Z are i.i.d. Bernoulli(ǫ). Let f be a
balanced Boolean function. Courtade and Kumar [4] conjected
that the dictator function maximizes the mutual information
I(X; f (Y )) between X and f (Y ). This is known as the most
informative Boolean function problem.
By the definition of mutual information, we have
I(X; f (Y )) = H(f (Y )) − H(f (Y )|X)
= 1 − E(H(Bernoulli(E[f (Y )|X]))).
The second identity follows from that f takes values either 0
or 1 and it is balanced. Owing to (Tǫ f )(X) = E[f (Y )|X], it
suffices to maximize −E(H(Bernoulli(Tǫ f ))), which is
E(Tǫ f log Tǫ f + Tǫ (1 − f ) log Tǫ (1 − f )).

(7)

If the dictator function maximizes the first term of (7), it
should also maximize the second term of (7), and vice versa.
Notice that
d
E(Tǫ f )p
= E(Tǫ f log Tǫ f ).
dp
p=1

As we know, E(Tǫ f ) = Ef is fixed, and E(Tǫ f )p is a
decreasing function of p for p > 1. Consider the Taylor
expansion of E(Tǫ f )p around p = 1, then Courtade and
Kumar’s Conjecture is equivalent to that the dictator function
maximizes the p-stability E(Tǫ f )p for p close to 1. This
closeness might depend on the dimension n. We have seen
that this p-stability statement holds for p = 1 and p = 2. So it
is reasonable to expect that the following stronger statement
holds.
Conjecture 4.1: For 1 ≤ p ≤ 2, the dictator function
maximizes E(Tǫ f )p among balanced Boolean functions.
Remark 4.1: Theorem 3.1 asserts that the above conjecture
holds when ǫ = ǫ(n) is close to 0 or 1/2. Therefore, Courtade
and Kumar’s Conjecture also holds in the low noise and the
high noise scenarios. As we mentioned in the introduction,
Samorodnitsky [17] verified Courtade and Kumar’s Conjecture
in the dimension-free high noise regime.
R EFERENCES
[1] N. H. Bshouty, J. C. Jackson, and C. Tamon. “Uniform-distribution
attribute noise learnability," Inform. and Comput., 187(2):277–290, 2003.
[2] I. Benjamini, G. Kalai, and O. Schramm. “Noise sensitivity of Boolean
functions and applications to percolation," Inst. Hautes Études Sci. Publ.
Math., (90):5–43 (2001), 1999.
[3] C. Borell. “Geometric bounds on the Ornstein-Uhlenbeck velocity
process," Z. Wahrsch. Verw. Gebiete, 70(1):1–13, 1985.
[4] T. A. Courtade and G. R. Kumar. “Which Boolean functions maximize
mutual information on noisy inputs?" IEEE Trans. Inform. Theory,
60(8):4515–4525, 2014.
[5] R. Eldan. “A two-sided estimate for the Gaussian noise stability deficit,"
Invent. Math., 201(2):561–624, 2015.
[6] L. H. Harper. “A necessary condition on minimal cube numberings," J.
Appl. Probability, 4:397–401, 1967.
[7] J. Håstad. “Some optimal inapproximability results," J. ACM, 48(4):798–
859, 2001.
[8] M. Isaksson and E. Mossel. “Maximally stable Gaussian partitions with
discrete applications," Israel J. Math., 189:347–396, 2012.
[9] J. Kahn, G. Kalai, and N. Linial. “The influence of variables on boolean
functions," in Proceedings of the 29th Annual IEEE Symposium on
Fundations of Computer Science, IEEE Computer Society Press, Los
Alamitos, CA,, pages 68–80, 1988.
[10] D. J. Kleitman. “Families of non-disjoint subsets," J. Combinatorial
Theory, 1:153–155, 1966.
[11] A. R. Klivans, R. O’Donnell, and R. A. Servedio. “Learning intersections and thresholds of halfspaces," J. Comput. System Sci., 68(4):808–
840, 2004.
[12] G. Kindler, R. O’Donnell, and D. Witmer.
“Remarks on the
most informative function conjecture at fixed mean,"
Available:
https://arxiv.org/abs/1506.03167.
[13] E. Mossel and R. O’Donnell. “Coin flipping from a cosmic source: on
error correction of truly random bits," Random Structures Algorithms,
26(4):418–436, 2005.
[14] E. Mossel, R. O’Donnell, O. Regev, J. E. Steif, and B. Sudakov. “Noninteractive correlation distillation, inhomogeneous Markov chains, and the
reverse Bonami-Beckner inequality," Israel J. Math., 154:299–336, 2006.
[15] R. O’Donnell. “Hardness amplification within NP," J. Comput. System
Sci., 69(1):68–94, 2004.
[16] G. Pichler, P. Piantanida, and Gerald Matz.
“Dictator
functions
maximize
mutual
information,"
Available:
https://arxiv.org/abs/1604.02109.
[17] A. Samorodnitsky. “On the entropy of a noisy function," IEEE Trans.
Inform. Theory, 62(10):5446–5464, 2016.
[18] K. Yang. “On the (im)possibility of non-interactive correlation distillation," Theoret. Comput. Sci., 382(2):157–166, 2007.

