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.{{cite journal|last1=Friedgut|first1=Ehud|last2=Kalai|first2=Gil|title=Every monotone graph property has a sharp threshold|journal=Proceedings of the American Mathematical Society|volume=124|issue=10|year=1996|pages=2993–3002|doi=10.1090/s0002-9939-96-03732-x|doi-access=free}}

Statement

For a function $f: \{-1,1\}^n \to \{-1,1\},$ note its Fourier expansion

: $f(x) = \sum_{S \subset [n]} \widehat{f}(S) x_S, \text{ where } x_S = \prod_{i \in S} 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{f}(S)^2,$

and the entropy $H$ (of the spectrum) is defined by

: $H(f) = - \sum_S \widehat{f}(S)^2 \log \widehat{f}(S)^2 ,$

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

References

[http://unsolvedproblems.org/ Unsolved Problems in Number Theory, Logic and Cryptography]
[http://cs.smith.edu/~orourke/TOPP/ The Open Problems Project], discrete and computational geometry problems

Category:Entropy

Category:Conjectures

Entropy influence conjecture

Statement

See also

References