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 
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á
Combinatorics and more 
Pingback: Sensitivity conjecture proved! | Windows On Theory
Good job!
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.”
And a nice comment by fred.
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 🙂 )
Pingback: Tools and Sensitivity | Gödel's Lost Letter and P=NP
Pingback: Twisted convolution and the sensitivity conjecture | What's new
Pingback: Spectral proofs of theorems on the boolean hypercube | Anurag's Math Blog
Pingback: Huangs’ Breakthrough, Cvetković’s Bound, Godsil’s Question, and Sinkovic’s Answer | Ratio Bound – A Combinatorics Blog
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – Digitado
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – 365 | Todas las noticias
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit | cursovt
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit - SonidoRD.com : SonidoRD.com
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – Tribuna Liberal
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit - PRESS.international
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – Gacetalibre
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.
Regarding Gotsman and Linial’s equivalence theorem indeed the implication 2′ ==> 2 is needed.
(2) For every boolean function
, 
,
(2′) For boolean function
of full degree 
, 
.
Proof of (2′)=>(2): Suppose a Boolean function
has degree 
, take a max monomial in 
, say 
define 
then 
has full degree 
, it follows form (2′) that 
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
, one of the induced subgraph has maximum degree at least 
.
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!
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – El Loco de la Colilla
Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit | KeepReading
Pingback: Amazing breakthrough in theory of computation | Aquazorcarson's Blog
Pingback: Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube. | Combinatorics and more
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.
Pingback: Two talks at HUJI: on the “infamous lower tail” and TOMORROW on recent advances in combinatorics | Combinatorics and more
Pingback: Greatest Hits 2015-2022, Part I | Combinatorics and more
Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more