Explore a 52-minute lecture on Boolean function analysis, focusing on the Fourier-Entropy Influence Conjecture. Delve into the characterization of Boolean functions with small total influence, a fundamental question in the field. Examine seminal results by Kahn-Kalai-Linial and Friedgut, addressing total influence K = o(log n). Learn about the outstanding Fourier-Entropy Conjecture by Friedgut and Kalai, which strengthens these results and remains relevant for k ≥ log n. Discover recent progress towards this conjecture, including the demonstration that functions with total influence K are concentrated on at most 2^O(K log K) distinct Fourier coefficients. Explore applications to learning theory and sharp thresholds. The lecture, presented by Dor Minzer from the Institute of Advanced Study, is based on joint work with Esty Kelman, Guy Kindler, Noam Lifshitz, and Muli Safra.
Overview
Syllabus
Introduction
Basics
Outline
Analysis
Moral Statement
New Results
Expressing Influences
Theorem
Recap
Taught by
Simons Institute