Sensitivity conjecture proved!

In a recent breakthrough, Hao Huang gave a 6 page paper proving the longstanding sensitivity conjecture. (Hat tip, Scott Aaronson and Gil Kalai. See this stackexchange post and this paper of Avishai for some links to the literature on this.)

The proof is beautiful and simple. I will write a few words here, but it is probably easier for you to just read the paper. The sensitivity conjecture was known to follow from the following statement: let be the Boolean Cube which is the degree graph on vertices identified with such that for every , if their Hamming distance is one. Then, the maximum degree of every subgraph of of size is at least .

Hao proves the above statement by showing that there is a signing of the adjacency matrix of that turns it into a matrix with eigenvalues equaling and eigenvalues equaling . That is, he shows (using a simple but clever inductive argument, see the 5 line proof of his Lemma 2.2) that there is an matrix with entries in whose nonzero entries correspond to the edges of the Boolean cube, and such that all the eigenvalues of are and they sum up to zero. (Note that this makes sense since should have the same Frobenius norm as the adjacency matrix of . The Frobenius norm squared is both the sum of squares of entries, which is for which is a degree graph, and also equal to the sum of squares of the eigenvalues, which is if all eigenvalues are .)

Once you have such a signing, the result follows from Cauchy’s Interlace Theorem that says that for every matrix and any matrix that is a principle sub-matrix of ,

where are the eigenvalues of and is the maximum eigenvalue of . A corollary of this (which is the only fact we need) is that if has its top eigenvalue with multiplicity (i.e., ), then every principle sub-matrix of order larger than will satisfy . (In fact, we only need .)

Indeed, suppose that is a subgraph of the Boolean cube of size . Then the principle submatrix of corresponding to the vertices of satisfies (since and the first eigenvalues of are ). But it’s easy to show that for every matrix the maximum eigenvalue of is upper bounded by the maximum norm of its rows, which in our case is the maximum degree of the graph .