Amazing: Hao Huang Proved the Sensitivity Conjecture!

Today’s arXived amazing paper by Hao Huang

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

Contains an amazingly short and beautiful proof of a famous open problem from the theory of computing – the sensitivity conjecture posed by Noam Nisan and Mario Szegedi

Hao Huang

Abstract: In this paper, we show that every $2^{n-1}+1$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt n$. This result is best possible, and improves a logarithmic lower bound shown by Chung, Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

The proof relies on the important relation found by Gotsman and Linial between the two problems mentioned in the abstract. It makes beautiful use of Cauchy’s interlace theorem (for eigenvalues).

Thanks to Noga Alon for telling me about the breakthrough. For more on the conjecture and a polymath project devoted to solving it, see this post on Aaronson’s Shtetl Optimized (SO).  See also this post on GLL.

Also today on the arXive a paper by Zuzana (Zuzka) Patáková and me: Intersection Patterns of Planar Sets. Like one of my very first papers “Intersection patterns of convex sets” the new paper deals with face numbers of nerves of geometric sets.

Links to further discussion of Huang’s breakthrough

See this new lovely post on SO (and don’t miss the excellent comment thread); and this post by Boaz Barak on WOT (Window on Theory) explains the main ingredient of Huang’s proof. Here is a post by Lance Fortnow on CC (Computational Complexity) mentioning a remarkable tweet by Ryan O’Donnell (see below the fold). Here is a comment by Hao on SO on the history of his own work on the problem since he heard it from Mike Saks in 2012.

More: And here is a lovely new post by Ken Regan on GLL, and here on Fedor Petrov’s new blog (congratulations, Fedya!) you can see the proof without the interlace theorem (as was also noted by Shalev Ben David); and here on CC Lance explains the proof of the Gotsman Linial reduction. (On Fedor’s blog you can find a combinatorial proof that  e⩽π!)

July, 25: An excellent QM (Quanta Magazine) article by Erica Klarreich. And another lovely post on GLL with a message that I and many other share: Huang’s new method is very very promising.

July 27-29: A great expository post on WN (What’s new) where Terry Tao presents the proof and describe a connection with Clifford algebras. It mentions a preprint by Roman Karasev where a connection of Huang’s “signed adjacency matrix” with exterior algebra is described. A connection of Huang’s “signing” of the edges of the discrete cube and Clifford algebras was also observed by  Tom Mrowka, and by Daniel Mathiews who used it to give a weighted generalization of the result.  Hao himself explains his motivation for the signing in a comment to Terry’s post.  In comment 83 on the SO thread, Vitor Bosshard points out a connection between Huang’s signing (actually, a small variation) and the Klee-Minty cube! Very interesting discussions of Huang’s proof in a wider persepective can be found in  Anurag math blog and also in the Ratio Bound the blog of (Ferdinand Ihringer). Anurag describes a related earlier work by Hao Huang, Oleksiy Klurman and Cosmin Pohoatato,  proving a theorem of Kleitman and various new extensions.

Don Knuth wrote a 1-page writeup of Huang’s proof. (Comment 85 on SO; he added “(but I’m not sure if God will vote for it)”. Wenjie Zheng (Comment 86 on SO) also wrote a post about it. Dima Pasechnik asked (comment 84): Does Huang’s matrix have a large monomial (i.e. signed permutation matrices) centraliser? Ferdinand Ihringer’s interesting and decorated comment over WN showed that there is a large body of research on pseudo-adjacency matrices of graphs with few eigenvalues. And over La Ciencia de la Mula Francis, el blog de Francisco R. Villatoro, “La conjetura de la sensibilidad ha sido demostrada.”

July 31: A very nice article by

Belated links on Yaroslav Shitov’s disproof of Hedetniemi’s conjecture

A few months ago we discussed Yaroslav Shitov’s disproof of Hedetniemi’s 1966 conjecture. Here are links to strengthening of the result by  Claude Tardif and Xuding Zhu and by by Xiaoyu He and Yuval Wigderson. And here is a lovely Quanta Magazine article by Erica Klarreich about it, ending with a quote by Noga Alon: “Sometimes, the reason that a conjecture is very hard to prove is simply that it is false.”

Ryan’s tweet

Another drawing from my paper with Zuzana Patáková

This entry was posted in Combinatorics, Computer Science and Optimization and tagged , . Bookmark the permalink.

24 Responses to Amazing: Hao Huang Proved the Sensitivity Conjecture!

1. Yishuo Shi says:

Good job!

2. Gil Kalai says:

Let me share with you Scott Aaronson’s added thought about the new breakthrough from his new post: “What this really is, is one of the purest illustrations I’ve seen in my career of the power and glory of the P≠NP phenomenon. We talk all the time about how proofs are easier to verify than to find. In practice, though, it can be far from obvious that that’s true. Consider your typical STOC/FOCS paper: writing it probably took the authors several months, while fully understanding the thing from scratch would probably take … also several months! If there’s a gap, it’s only by a factor of 4 or 5 or something. Whereas in this case, I don’t know how long Huang spent searching for the proof, but the combined search efforts of the community add up to years or decades. The ratio of the difficulty of finding to the difficulty of completely grasping is in the hundreds of thousands or millions.”

• Gil Kalai says:

And a nice comment by fred.

“The ratio of the difficulty of finding to the difficulty of completely grasping is in the hundreds of thousands or millions”

It’s not that different than Alpha Go Zero taking a couple of hours (from scratch) to come up with observable novel tactics that human experts had overlooked for thousands of years.

My take: Scott and Fred are both correct. This can be seen as a nice example of the P≠NP phenomenon, but this manifestation of the phenomenon is strictly within P (or BPP, if you prefer) . The phenomenon is that it is easier to verify than to prove. But everything we (or alpha zero) can prove is within BPP (quantum supremacy notwithstanding 🙂 )

3. Dear Prof Kalai,

I tried to read the paper by Gotsman and Linial but was puzzled by their proof the equivalence theorem. In particular I don’t see how 2 was equivalent to 2’ in their proof. It’s tricial that 2 implies 2’ but 2’ seems to be only about the special case where the degree of f is n, the number of its variables. Without the reverse direction the polynomial equivalence is degree and sensitivity seems to break down. Could you help me make sense of the subtlety behind it? Thanks.

• Gil Kalai says:

Regarding Gotsman and Linial’s equivalence theorem indeed the implication 2′ ==> 2 is needed.

(2) For every boolean function $f$, $s(f)\ge h(deg(f))$,

(2′) For boolean function $g$ of full degree $n$, $s(g)\ge h(n)$.

Proof of (2′)=>(2): Suppose a Boolean function $f$ has degree $d$, take a max monomial in $f$, say $x_1\cdots x_d,$ define $g(x_1,...,x_d)=f(x_1,...,x_d,0,...0),$ then $g$ has full degree $d$, it follows form (2′) that $s(f) \ge s(g) \ge h(d)=h(deg(f)).$

As a reminder for the rest of the argument , consider also the following statement that Huang proved in his recent paper:

(1) For a unbalanced partition of $Q^n$, one of the induced subgraph has maximum degree at least $h(n)$.

What we need here is (1)=>(2′)=>(2). We saw (2″) ==> (2). The implication (1)=>(2′) follows from multiplying the Boolean function with the parity function.

• Can’t believe I am so obtuse. Thanks for the clarification!

4. Rohan says:

Hello Prof. Kalai.

I may be a bit late here, but I too was reading Gotsman and Linial’s paper proving the equivalence of the sensitivity conjecture in graph-theoretic terms. My question is this:
I don’t see how in the proof of the equivalence theorem, that condition 1′ implies condition 1. In particular, I have a doubt as to why E(g) shouldn’t be equal to 0 have a bearing on the theorem.

Hope you could shed some light on this, sir. Thanks.