Dor Minzer

MIT

Time:

Monday, April 4, 2022 - 12:00pm

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.