Advances in Boolean Function Analysis — On the Fourier-Entropy Influence Conjecture

This talk is part of the Advances in Boolean Function Analysis Lecture Series. The series will feature weekly two-hour lectures that aim to address both the broad context of the result and the technical details. Though closely related in theme, each lecture will be self-contained. Join us weekly at 10:00 a.m. PDT, from July 15, 2020 to August 18, 2020. There is a five minute break at the end of the first hour.

Abstract:

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.