In mathematics, the entropy influence conjecture is a statement about

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...

s originally conjectured by Ehud Friedgut and

Gil Kalai Gil Kalai (born 1955) is the Henry and Manya Noskwith Professor Emeritus of Mathematics at the Hebrew University of Jerusalem, Israel, Professor of Computer Science at the Interdisciplinary Center, Herzliya, and adjunct Professor of mathematics a ...

in 1996.

Statement

For a function

f: \^n \to \,

note its

Fourier expansion A Fourier series () is a summation of harmonically In music, harmony is the process by which individual sounds are joined together or composed into whole units or compositions. Often, the term harmony refers to simultaneously occurring frequ ...

f(x) = \sum_ \widehat(S) x_S, \text x_S = \prod_ x_i.

The entropy–influence conjecture states that there exists an absolute constant ''C'' such that

H(f) \leq C I(f),

where the total influence

I

is defined by :

I(f) = \sum_S , S,  \widehat(S)^2,

and the entropy

H

(of the spectrum) is defined by :

H(f) = - \sum_S \widehat(S)^2 \log \widehat(S)^2 ,

(where ''x'' log ''x'' is taken to be 0 when ''x'' = 0).

References

Unsolved Problems in Number Theory, Logic and Cryptography

The Open Problems Project
discrete and computational geometry problems {{DEFAULTSORT:Entropy Influence Conjecture Entropy Conjectures

Statement

See also

References