Entropy influence conjecture

In mathematics, the entropy influence conjecture is a statement about Boolean functions originally conjectured by Ehud Friedgut and Gil Kalai in 1996.

Statement

For a function note its Fourier expansion

The entropy–influence conjecture states that there exists an absolute constant C such that where the total influence is defined by

and the entropy (of the spectrum) is defined by

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

See also

• Analysis of Boolean functions

References

• Unsolved Problems in Number Theory, Logic and Cryptography
• The Open Problems Project, discrete and computational geometry problems