Misplaced Pages

Entropy influence conjecture

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (April 2011) (Learn how and when to remove this message)

In mathematics, the entropy influence conjecture is a statement about Boolean functions originally conjectured by Ehud Friedgut and Gil Kalai in 1996.

Statement

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

f ( x ) = ∑ S ⊂ [ n ] f ^ ( S ) x S ,  where  x S = ∏ i ∈ S x i . {\displaystyle f(x)=\sum _{S\subset }{\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 H ( f ) ≤ C I ( f ) , {\displaystyle H(f)\leq CI(f),} where the total influence I {\displaystyle I} is defined by

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

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

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

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

See also

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