The Entropy Influence Conjecture Revisited

Show simple item record

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 Influence (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 Influence of the function. The conjecture has been proven for families of functions of smaller sizes. O’donnell, Wright and Zhou (ICALP’11)[7] verified 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 satisfies 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.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account