Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR11-146 | 1st November 2011 14:12

#### The Entropy Influence Conjecture Revisited

TR11-146
Authors: Bireswar Das, Manjish Pal, Vijay Visavaliya
Publication: 2nd November 2011 21:44
In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$
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)\cite{KLW10}. 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$.