Sensitivity theorem
Theorem about complexity measures of Boolean functions / From Wikipedia, the free encyclopedia
In computational complexity, the sensitivity theorem, proved by Hao Huang in 2019,[1] states that the sensitivity of a Boolean function is at least the square root of its degree, thus settling a conjecture posed by Nisan and Szegedy in 1992.[2] The proof is notably succinct, given that prior progress had been limited.[3]