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.

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 CI(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

References

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