Sensitivity Conjecture and Its Applications

Explore the groundbreaking resolution of the Sensitivity Conjecture in theoretical computer science through this illuminating lecture. Delve into the background of various complexity measures for Boolean functions and understand why the Sensitivity Conjecture remained a mystery for nearly 30 years. Follow a step-by-step explanation of the linear algebraic proof based on the Gotsman-Linial reduction, which solved this long-standing problem. Gain insights into the significance of this breakthrough, its historical context, and the best bounds and separations previously known. Examine the Gotsman-Linial equivalence, upper and lower bounds, and the main theorem. Learn about eigenvalue interlacing, signed adjacency matrices, and the innovative approach used in the 6-page paper that cracked the conjecture. Conclude by exploring corollaries, extensions, and exciting future research problems in this field of theoretical computer science.

Intro
Sensitivity and block sensitivity (0)
The Rubinstein function (1)
What is the significance of the Sensitivity Conjecture?
History: best bounds and separations
The Gotsman-Linial equivalence (1)
Just above half
Upper and lower bounds
The main theorem
The largest eigenvalue of graphs
Eigenvalue interlacing (11)
Signed adjacency matrix
One way to choose the signed matrix In the 6-page paper
Corollaries and extensions
Future research problems