Entropy influence conjecture
Appearance
![]() | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (April 2011) |
In mathematics, the entropy influence conjecture is a statement about Boolean functions originally conjectured by Ehud Friedgut and Gil Kalai in 1996.[1]
Statement
[edit]For a function note its Fourier expansion
The entropy–influence conjecture states that there exists an absolute constant C such that where the total influence is defined by
and the entropy (of the spectrum) is defined by
(where x log x is taken to be 0 when x = 0).
See also
[edit]References
[edit]- ^ 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