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)
