[This post is authored by Gil Kalai, who has kindly “guest blogged” this week’s “open problem of the week”. - T.]
The entropy-influence conjecture seeks to relate two somewhat different measures as to how a boolean function has concentrated Fourier coefficients, namely the total influence and the entropy.
We begin by defining the total influence. Let 
be the discrete cube, i.e. the set of 
vectors 
of length n. A boolean function is any function 
from the discrete cube to {-1,+1}. One can think of such functions as “voting methods”, which take the preferences of n voters (+1 for yes, -1 for no) as input and return a yes/no verdict as output. For instance, if n is odd, the “majority vote” function 
returns +1 if there are more +1 variables than -1, or -1 otherwise, whereas if 
, the “
dictator” function returns the value 
of the variable.
We give the cube the uniform probability measure 
(thus we assume that the n voters vote randomly and independently). Given any boolean function f and any variable , define the influence 
of the variable to be the quantity
where 
is the element of the cube formed by flipping the sign of the variable. Informally, measures the probability that the voter could actually determine the outcome of an election; it is sometimes referred to as the Banzhaf power index. The total influence I(f) of f (also known as the average sensitivity and the edge-boundary density) is then defined as
Thus for instance a dictator function has total influence 1, whereas majority vote has total influence comparable to 
. The influence can range between 0 (for constant functions +1, -1) and n (for the parity function 
or its negation). If f has mean zero (i.e. it is equal to +1 half of the time), then the edge-isoperimetric inequality asserts that 
(with equality if and only if there is a dictatorship), whilst the Kahn-Kalai-Linial (KKL) theorem asserts that 
for some k. There is a result of Friedgut that if 
is bounded by A (say) and 
, then f is within a distance 
(in 
norm) of another boolean function g which only depends on 
of the variables (such functions are known as juntas).
Read the rest of this entry »
Recent Comments