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.

Uses your system voice; voice and rate in settings.

Snapshot

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

Provenance

snapshot enwiki-001117960858 · captured 2022-10-24 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Entropy influence conjecture”, snapshot enwiki-001117960858. https://encyclopegia.org/a/entropy-influence-conjecture

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.