The Sensitivity Theorem

The sensitivity theorem (former sensitivity conjecture) relates multiple ways to quantify the complexity, or lack of "smoothness", of a boolean function f: {0,1}ⁿ → {0,1}:  The minimum degree of a polynomial p(x): Rⁿ → R that extends f, the sensitivity s(f), and the block sensitivity bs(f).

In 2019, H. Huang solved the conjecture with a remarkably short proof. I will give a self-contained explanation of this proof, and motivate the importance of the (former) conjecture by relating it to other measures of complexity for boolean functions.