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] Several papers in the late 1980s and early 1990s[4][5][6][7] showed that various decision tree complexity measures of Boolean functions are polynomially related, meaning that if
Their proof went via yet another complexity measure, block sensitivity, which had been introduced by Nisan.
This is equivalent to asking whether sensitivity is polynomially related to the various decision tree complexity measures, as well as to degree, approximate degree, and other complexity measures which have been shown to be polynomially related to these along the years.
[13] Along the years, several special cases of the sensitivity conjecture were proven.
[14][15] The sensitivity theorem was finally proven in its entirety by Huang,[1] using a reduction of Gotsman and Linial.
can be expressed in a unique way as a multilinear polynomial.
is the degree of this unique polynomial, denoted
The sensitivity theorem states that In the other direction, Tal,[17] improving on an earlier bound of Nisan and Szegedy,[2] showed that The sensitivity theorem is tight for the AND-of-ORs function:[18] This function has degree
in the unique multilinear polynomial representing
If we substitute an arbitrary value in the coordinates not mentioned in the monomial then we get a function
in which two vertices are connected if they differ by a single coordinate) induced by
In order to prove the sensitivity theorem, it suffices to show that
This reduction is due to Gotsman and Linial.
This means that there is a way to assign a sign to every edge of the hypercube so that this property is satisfied.
The property that the product of the signs in every square is
) intersects the space of vectors supported by
(This is a simplification of Huang's original argument due to Shalev Ben-David.
is at most the sum of absolute values of all neighbors of
Huang[1] constructed the signing recursively.
for the other, and assign all edges between the two copies the sign
The sensitivity theorem can be equivalently restated as Laplante et al.[21] refined this to where
They showed furthermore that this bound is attained at two neighboring points of the hypercube.
Aaronson, Ben-David, Kothari and Tal[22] defined a new measure, the spectral sensitivity of
This is the largest eigenvalue of the adjacency matrix of the sensitivity graph of
They showed that Huang's proof can be decomposed into two steps: Using this measure, they proved several tight relations between complexity measures of Boolean functions:
Dafni et al.[23] extended the notions of degree and sensitivity to Boolean functions on the symmetric group and on the perfect matching association scheme, and proved analogs of the sensitivity theorem for such functions.
Their proofs use a reduction to Huang's sensitivity theorem.