Speaker:
Institution:
Time:
Location:
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.