Simons Institute Lecture: Advances in Boolean Function Analysis

  • Remote Access Enabled - Zoom
  • Virtual Presentation
  • Postdoctoral Researcher
  • School of Mathematics
  • Institute of Advanced Study

On the Fourier-Entropy Influence Conjecture

Begins 10:00 am PDT / 1:00 pm EDT

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 $. 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. 

Zoom Participation Enabled.

The Simons Institute for the Theory of Computing  (Berkeley) is organizing a series of lectures on Advances in Boolean Function Analysis, that will highlight a few major developments in the area. The series will feature weekly two-hour lectures from July 15 to Aug 18. The lectures aim to address both the broad context of the results and their technical details. Though closely related in theme, each lecture will be self-contained.