Friedgut–Kalai entropy/influence conjecture
Friedgut–Kalai entropy/influence conjecture
Let be a Boolean function on the discrete cube with uniform measure . Write for the entropy of its Fourier-weight distribution and for its total influence. Friedgut–Kalai's conjecture. There exists a universal constant such that, for every and every such ,
If true, this would imply strong lower bounds on total influence for graph properties and consequences for Fourier concentration of polynomial-size DNF formulas. The paper states that the conjecture was still wide open, with the best cited graph-property lower bound being for every .
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Nathan Keller, Elchanan Mossel and Tomer Schlank, “A Note on the Entropy/Influence Conjecture”, arXiv:1105.2651 (2011).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.