Sensitivity conjecture proved!

~ Boaz Barak

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 G_n be the Boolean Cube which is the degree n graph on N=2^n vertices identified with \{0,1\}^n such that for every x,y\in \{0,1\}^n, x \sim y if their Hamming distance is one. Then, the maximum degree of every subgraph H of G_n of size >N/2 is at least \sqrt{n}.

Hao proves the above statement by showing that there is a signing of the N\times N adjacency matrix of G_n that turns it into a matrix with N/2 eigenvalues equaling +\sqrt{n} and N/2 eigenvalues equaling -\sqrt{n}. 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 N\times N matrix A with entries in \{ 0, \pm 1 \} whose nonzero entries correspond to the edges of the Boolean cube, and such that all the N eigenvalues of A are \pm \sqrt{n} and they sum up to zero. (Note that this makes sense since A should have the same Frobenius norm as the adjacency matrix of G_n. The Frobenius norm squared is both the sum of squares of entries, which is N\cdot n for G_n which is a degree n graph, and also equal to the sum of squares of the eigenvalues, which is N\cdot n if all eigenvalues are \pm \sqrt{n}.)

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

\lambda_{1+N-M}(A) \leq \lambda_1(B) \leq \lambda_1(A)

where \lambda_1(A) \geq \lambda_2(A) \cdots \geq \lambda_N(A) are the eigenvalues of A and \lambda_1(B) is the maximum eigenvalue of B. A corollary of this (which is the only fact we need) is that if A has its top eigenvalue \lambda_1(A) with multiplicity K (i.e., \lambda_1(A)=\lambda_K(A)), then every principle sub-matrix B of order larger than N-K will satisfy \lambda_1(B) = \lambda_1(A). (In fact, we only need \lambda_1(B) \geq \lambda_1(A).)

Indeed, suppose that H is a subgraph of the Boolean cube of size M>N/2. Then the principle submatrix B of A corresponding to the vertices of H satisfies \lambda_1(B) \geq \lambda_{1+N-M}(A) = \sqrt{n} (since M>N/2 and the first N/2 eigenvalues of A are +\sqrt{n}). But it’s easy to show that for every matrix B the maximum eigenvalue of B is upper bounded by the maximum \ell_1 norm of its rows, which in our case is the maximum degree of the graph H.

Published by Boaz Barak

4 thoughts on “Sensitivity conjecture proved!”

  1. Pingback: Amazing: Hao Huang Proved the Sensitivity Conjecture! | Combinatorics and more

  2. Great result…great post

    That there is a short proof of a long conjectured result is cool. It gives one hope that perhaps other results are possible.

    Dick

    Reply
  3. Pingback: Tools and Sensitivity | Gödel's Lost Letter and P=NP

Leave a comment