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]

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

${\displaystyle f(x)=\sum _{S\subset [n]}\hat{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 ${\displaystyle H(f)\le CI(f),}$ where the total influence ${\displaystyle I}$ is defined by

${\displaystyle I(f)=\sum _S|S|\hat{f}(S{)}^2,}$

and the entropy ${\displaystyle H}$ (of the spectrum) is defined by

${\displaystyle H(f)=-\sum _S\hat{f}(S{)}^2\log \hat{f}(S{)}^2,}$

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

• Analysis of Boolean functions

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

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Entropy influence conjecture. Read more