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]

## Statement

For a function [math]\displaystyle{ f: \\{-1,1\\}^n \to \\{-1,1\\}, }[/math] note its Fourier expansion

[math]\displaystyle{ f(x) = \sum_{S \subset [n]} \widehat{f}(S) x_S, \text{ where } x_S = \prod_{i \in S} x_i. }[/math]

The entropy–influence conjecture states that there exists an absolute constant C such that [math]\displaystyle{ H(f) \leq C I(f), }[/math] where the total influence [math]\displaystyle{ I }[/math] is defined by

[math]\displaystyle{ I(f) = \sum_S |S| \widehat{f}(S)^2, }[/math]

and the entropy [math]\displaystyle{ H }[/math] (of the spectrum) is defined by

[math]\displaystyle{ H(f) = - \sum_S \widehat{f}(S)^2 \log \widehat{f}(S)^2 , }[/math]

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

## See also

* Analysis of Boolean functions

## References

1. ↑ Friedgut, Ehud; Kalai, Gil (1996). "Every monotone graph property has a sharp threshold". Proceedings of the American Mathematical Society 124 (10): 2993–3002. doi:10.1090/s0002-9939-96-03732-x.

* 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

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Entropy_influence_conjecture&oldid=2627530"