Fourier concentration conjecture for low-influence Boolean functions
Fourier concentration conjecture for low-influence Boolean functions
Fix . Let be a Boolean function, let denote its total influence, and let be its Fourier coefficients. Fourier concentration conjecture. There exists a constant such that, for every , every , and every such , there is a set satisfying
and
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
Sign in to submit a solution.
No solutions have been posted yet.