Events Summer 2020

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

Wednesday, July 15th, 2020, 10:00 am12:00 pm

Add to Calendar


Dor Minzer (Institute of Advanced Study)


Full participation (including the capacity to ask questions) will be available via Zoom webinar

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.

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.