This article describes the The Entropy Influence Conjecture.
For a function
f
:
{
−
1
,
1
}
n
→
{
−
1
,
1
}
the Entropy-Influence relates the following two quantities, both of which may be expressed in terms of the Fourier Expansion of the functions
f
=
∑
S
⊂
[
n
]
f
^
(
S
)
x
S
, where
x
S
=
∏
i
∈
S
x
i
. The first expression is the total influence of the function defined by
I
(
f
)
=
∑
S
|
S
|
f
^
2
(
S
)
. The second terms is the Entropy (of the spectrum) of the function defined by
H
(
f
)
=
−
∑
S
f
^
2
(
S
)
log
f
^
2
(
S
)
(where
x
log
x
=
0
when
x
=
0
).
The conjecture states that there exists an absolute constant C such that for all Boolean functions
f
:
{
−
1
,
1
}
n
→
{
−
1
,
1
}
it holds that
H
(
f
)
≤
C
I
(
f
)
.
