Fourier concentration conjecture for low-influence Boolean functions

From papers

Fix 0<p<10<p<1. Let f:{1,1}pn{1,1}f:\{-1,1\}^n_p\to\{-1,1\} be a Boolean function, let I(f)\operatorname{I}(f) denote its total influence, and let f^(S)\hat f(S) be its Fourier coefficients. Fourier concentration conjecture. There exists a constant C(p)>0C(p)>0 such that, for every ϵ>0\epsilon>0, every nn, and every such ff, there is a set Bϵ{0,1}nB_\epsilon\subset\{0,1\}^n satisfying

logBϵC(p)I(f)\log|B_\epsilon|\leq C(p)\,\operatorname{I}(f)

and

SBϵf^(S)2<ϵ.\sum_{S\notin B_\epsilon}\hat f(S)^2<\epsilon.

This conjecture would strengthen the Fourier-concentration conclusion in Friedgut's low-influence characterization: most Fourier weight would lie on at most exponentially many coefficients in the total influence. The source presents it as an open conjecture resembling Bourgain–Kalai's theorem.

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.