Resolution of the Sensitivity Conjecture: where linear algebra meets combinatorics

Many complexity measures of Boolean functions have been well studied in Theoretical Computer Science. These include sensitivity, block sensitivity, degree, approximate degree, certificate complexity, decision-tree complexity, among many others. It has been long known that almost all these measures are polynomially related to each other, yet whether sensitivity belongs to the same class (known as the Sensitivity Conjecture) had remained a mystery for almost three decades until July 2019. In this talk, I will explain the background and history of the Sensitivity Conjecture, and walk through a very short proof based on undergraduate level linear algebra and combinatorics.