The Sensitivity Conjecture is True

Suhail Sherif
Anamay Tengse
Friday, 26 Jul 2019, 17:15 to 18:15
A-201 (STCS Seminar Room)
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)