Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.