The Entropy Influence Conjecture Revisited

Details The Entropy Influence Conjecture Revisited The Entropy Influence Conjecture Revisited

2011-10-19

arxiv.org/abs/1110.4301v2

Mathematics

Combinatorics

We thank Kunal Dutta and Justin Salez for pointing out that our result can be extended to a high probability statement

Scientific paper

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$ satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96). The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of the function. The conjecture has been proven for families of functions of smaller sizes. O'donnell, Wright and Zhou (ICALP'11) verified the conjecture for the family of symmetric functions, whose size is $2^{n+1}$. They are in fact able to prove the conjecture for the family of $d$-part symmetric functions for constant $d$, the size of whose is $2^{O(n^d)}$. Also it is known that the conjecture is true for a large fraction of polynomial sized DNFs (COLT'10). Using elementary methods we prove that a random function with high probability satisfies the conjecture with the constant as $(2 + \delta)$, for any constant $\delta > 0$.

Affiliated with

Also associated with

No associations

Rating

The Entropy Influence Conjecture Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Entropy Influence Conjecture Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Entropy Influence Conjecture Revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-597453