Friedgut–Kalai entropy/influence conjecture

From papers

Let f:0,1n1/2{1,1}f:0,1n_{1/2}\to\{-1,1\} be a Boolean function on the discrete cube with uniform measure μ1/2\mu_{1/2}. Write Ent1/2(f)\operatorname{Ent}_{1/2}(f) for the entropy of its Fourier-weight distribution and I1/2(f)\operatorname{I}_{1/2}(f) for its total influence. Friedgut–Kalai's conjecture. There exists a universal constant cc such that, for every nn and every such ff,

Ent1/2(f)cI1/2(f).\operatorname{Ent}_{1/2}(f)\leq c\,\operatorname{I}_{1/2}(f).

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 Ω((logn)2ϵ)\Omega((\log n)^{2-\epsilon}) for every ϵ>0\epsilon>0.

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

No solutions have been posted yet.