On the Fourier-Entropy Conjecture


Dor Minzer




Monday, April 4, 2022 - 12:00pm


Zoom: https://sites.google.com/view/paw-seminar

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.


Subscribe to RSS - Probability and Analysis Webinar