Advances in Boolean Function Analysis — On the Fourier-Entropy Influence Conjecture
16Dor Minzer (Institute of Advanced Study)
https://simons.berkeley.edu/events/boolean-1
Characterizing Boolean functions with small total influence is one of the most fundamental questions in analysis of Boolean functions. The seminal results of Kahn-Kalai-Linial and of Friedgut address this question for total influence $K = o(\log n)$, and show that a function with total influence $K$ (essentially) depends on $2^{O(K)}$ variables.
The Fourier-Entropy Conjecture of Friedgut and Kalai is an outstanding conjecture that strengthens these results, and remains meaningful for $k \geq \log n$. Informally, the conjecture states that the Fourier transform of a function with total influence $K$, is concentrated on at most $2^{O(K)}$ distinct characters.
In this talk, we will discuss recent progress towards this conjecture. We show that functions with total influence $K$ are concentrated on at most $2^{O(K\log K)}$ distinct Fourier coefficients. We also mention some applications to learning theory and sharp thresholds.
Based on a joint work with Esty Kelman, Guy Kindler, Noam Lifshitz and Muli Safra.