Date

Nov 16, 2021 3:00 PM — 4:00 PM

Location

[PST] UCLA Participating Analysis Seminar

he sensitivity theorem (former sensitivity conjecture) relates multiple ways to quantify the complexity, or lack of “smoothness”, of a boolean function f:{0,1}^n -> f : The minimum degree of a polynomial p(x):R^n -> 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.