The Sensitivity Conjecture is True

Abstract: Decision trees form a basic model of computation, with connections to many areas in complexity and approximation theory. The decision tree complexity D(f) of a Boolean function f is the number of bits of the input you have to query in order to determine the value of f on that input.

It is easy to see that it is hard for a decision tree to differentiate between the input being a specific string s and the input being different from s in 1 bit. Turning this into a lower bound method yields the sensitivity bound s(f). A slightly more generalized lower bound method that also follows from this is the block sensitivity bound bs(f). Hence s(f) <= bs(f) <= D(f).

In 1989 Nisan showed that block sensitivity is a tight lower bound, in the sense that D(f) <= bs(f)^4, and Nisan and Szegedy floated the conjecture that sensitivity is also a tight lower bound. This conjecture has received a lot of attention for its fundamental nature and for how simple-sounding it is. Scott Aaronson called it "one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science."

Earlier this month, Hao Huang came up with a remarkably short and simple proof of the conjecture, using a graph theoretic approach suggested by Gotsman and Linial in 1992. This proof is what I plan to present in this seminar.