# The Entropy Influence Conjecture Revisited

 dc.contributor.author Das, Bireswar dc.contributor.author Pal, Manjish dc.contributor.author Visavaliya, Vijay dc.date.accessioned 2014-03-24T18:31:30Z dc.date.available 2014-03-24T18:31:30Z dc.date.issued 2011-10 dc.identifier.citation Das, Bireswar; Pal, Manjish and Visavaliya, Vijay, “The entropy influence conjecture revisited”, arXiv, Cornell University Library,DOI: http://arxiv.org/abs/1110.4301, Oct. 2011. en_US dc.identifier.uri arXiv:1110.4301 dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/985 dc.description.abstract 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. en_US dc.description.statementofresponsibility by Bireswar Das, Manjish Pal and Vijay Visavaliya dc.language.iso en en_US dc.publisher arXiv, Cornell University Library en_US dc.subject Combinatorics en_US dc.subject Computational complexity en_US dc.subject Discrete mathematics en_US dc.subject Fourier entropy influence en_US dc.title The Entropy Influence Conjecture Revisited en_US dc.type Preprint
﻿

## Files in this item

Files Size Format View

There are no files associated with this item.