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

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
  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.