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.
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 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).
See also
Analysis of Boolean functions
Text derived from https://en.wikipedia.org/w/index.php?oldid=1117960858 under CC BY-SA 4.0; modifications have been made.