Sensitivity Conjecture and Its Applications

Hao Huang (Emory University) & Avishay Tal (UC Berkeley)
Advances in Boolean Function Analysis

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 (a.k.a. the Sensitivity Conjecture of Nisan and Szegedy) has remained a mystery for almost three decades until last July.

In this talk, we will explain some background, walk through a linear algebraic proof of the Sensitivity Conjecture based on the Gotsman-Linial reduction to an extremal combinatorial problem on discrete cubes, and discuss the remaining challenges.