Analysis of Boolean functions is a fundamental tool in a theorist’s toolkit, one that has innumerable applications in almost all areas of theoretical computer science ranging from learning theory, hardness of approximation, circuit complexity, pseudorandomness, and quantum computation. It was a major focus of one of the first programs at the Simons Institute, Real Analysis in Computer Science.
Over the past couple of years, the field of analysis of Boolean functions has seen several major advances. Long-standing open questions like the sensitivity conjecture have been resolved, and there has been substantial progress on others such as the sunflower lemma and Fourier entropy conjecture. There has been an influx of new ideas from areas such as stochastic calculus. This online lecture series aims to highlight some of these major developments.
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. Dates, speakers, and titles are listed below.
- Wednesday, July 15: Dor Minzer (Institute of Advanced Study) — On the Fourier-Entropy Influence Conjecture
- Wednesday, July 22: Hao Huang (Emory University) & Avishay Tal (UC Berkeley) — Sensitivity Conjecture and Its Applications
- Monday, August 3: Shachar Lovett (UC San Diego) — Improved Bounds for the Sunflower Lemma
- Wednesday, August 5: Ronen Eldan (Weizmann Institute) — Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis
- Wednesday, August 12: Esty Kelman (Tel Aviv University) — KKL via Random Restrictions
- Tuesday, August 18: Pooya Hatami (Ohio State University) — Pseudorandom Generators from Polarizing Random Walks