Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and me in 1996. (See this blog post from 2007.)
Abstract: The total inﬂuence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total inﬂuence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total inﬂuence is o(logn), however, both results become useless when the total inﬂuence of the function is ω(logn). The only case in which this logarithmic barrier has been broken for an interesting class of function was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of .
In this paper, we revisit the key ideas of the Bourgain-Kalai paper. We prove a new general inequality that upper bounds the correlation between a Boolean function f and a real-valued, low degree function g in terms of their norms, Fourier coefﬁcients and total inﬂuences.
Some corollaries of this inequality are:
- The Bourgain-Kalai result.
- A slightly weaker version of the Fourier-Entropy Conjecture. More precisely, we prove that the Fourier entropy of the low-degree part of f is at most , where I[f] is the total inﬂuence of f. In particular, we conclude that the Fourier spectrum of a Boolean function is concentrated on at most Fourier coefﬁcients.
- Using well-known learning algorithms of sparse functions, the previous point implies that the class of functions with sub-logarithmic total inﬂuence (i.e. at most is learnable in polynomial time, using membership queries.
A few remarks:
A) Given a Boolean function let be its Fourier-Walsh expansion. (Here .) The total influence of is described by
The spectral entropy of is defined by
The entropy-influence conjecture (here called the Fourier-entropy conjecture) asserts that for some universal constant C
B) One interesting feature of the conjecture is that the RHS is invariant under arbitrary linear transformations of (regarded as an -dimensional vector space) while the LHS is invariant only to permutations of the variables.
C) My paper with Jean Bourgain, Influences of variables and threshold intervals under group symmetries, describes lower bounds on total influences for Boolean function invariant under certain groups of permutations (of the variables). Those results are stronger (but more restrictive) than what the Entropy/influence conjecture directly implies. (This was overlooked for a while.) The new paper gives (much hoped for, see below) simpler proofs and stronger results compared to those in my paper with Jean Bourgain.
D) Ryan O’Donnel wrote about Bourgain and some of his contributions to the analysis of Boolean functions:
“I spent close to 5 years understanding one 6-page paper of his (“On the distribution of the Fourier spectrum of Boolean functions”), and also close to 10 years understanding a 10-page paper of his (the k-SAT sharp threshold ‘appendix’). If anyone’s up for a challenge, I’m pretty sure no one on earth fully understands the second half of his paper “Influences of variables and threshold intervals under group symmetries” with Kalai (including Gil 🙂 )”
It looks that by now we have pretty good understanding and even some far-reaching progress regarding all three papers that Ryan mentioned. (It is unclear if we can hope now for an exponential spread of understanding for Bourgain’s proofs.)