The Entropy Influence Conjecture Revisited

In this paper, we prove that most of the boolean functions, f : {?1, 1} n ? {?1, 1}satisfy the Fourier Entropy In?uence (FEI) Conjecture due to Friedgut and Kalai(Proc. AMS�96)[1]. The conjecture says that the Entropy of a boolean function is at most a constant times the In?uence of the function. The conjecture has been proven for families of functions of smaller sizes. O�donnell, Wright and Zhou (ICALP�11)[7] veri?ed the conjecture for the family of symmetric functions, whose size is 2n+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 2O(nd). Also it is known that the conjecture is true for a large fraction of polynomial sized DNFs (COLT�10)[5]. Using elementary methods we prove that a random function with high probability satis?es the conjecture with the constant as (2 + ?), for any constant ? > 0.