Entropy influence conjecture explained

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

Statement

For a function

f: \{ -1 , 1 \} ^{n} \to \{ -1 , 1 \}, note its Fourier expansionf(x) = \sum _{S} \widehat{f}(S) x _{S,} where x _{S} = \prod _{i} 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 byI(f) = \sum _{S} |S| \widehat{f}(S) ^{2,}

and the entropy

H (of the spectrum) is defined byH(f) = - \sum _{S} \widehat{f}(S) ^{2} log \widehat{f}(S) ^{2} ,

(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

Notes and References

1. Friedgut. Ehud. Kalai. Gil. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society. 124. 10. 1996. 2993–3002. 10.1090/s0002-9939-96-03732-x. free.