TR11-146 Authors: Bireswar Das, Manjish Pal, Vijay Visavaliya

Publication: 2nd November 2011 21:44

Downloads: 4460

Keywords:

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)\cite{FG96}. 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)\cite{DWZ11} 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)\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$.