Entropy influence conjecture

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

${\displaystyle 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 ${\displaystyle H(f)\leq CI(f),}$ where the total influence ${\displaystyle I}$ is defined by

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

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

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

(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