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 f:{−1,1}n->{−1,1}, note its Fourier expansion

f(x)=∑S⊂[n]f^(S)xS, where xS=∏i∈Sxi.

The entropy–influence conjecture states that there exists an absolute constant C such that H(f)≤CI(f), where the total influence I is defined by

I(f)=∑S|S|f^(S)2,

and the entropy H (of the spectrum) is defined by

H(f)=−∑Sf^(S)2log⁡f^(S)2,

(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=245509"