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 ...

in 1996.

Statement

For a function

f: \^n \to \,

note its

Fourier expansion A Fourier series () is a summation of harmonically related sinusoidal functions, also known as components or harmonics. The result of the summation is a periodic function whose functional form is determined by the choices of cycle length (or ''p ...

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