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 Rafi Letzter on LiveScience.  A quote by me: “Huang took this matrix, and he modified it in a very ingenious and mysterious way,” Kalai said. “It’s like you have an orchestra and they play some music, and then you let some of the players, I don’t know, stand on their head, and the music becomes completely different — something like that.”

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á

 

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

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

  1. Pingback: Sensitivity conjecture proved! | Windows On Theory

  2. Yishuo Shi says:

    Good job!

  3. 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 🙂 )

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

  5. Pingback: Twisted convolution and the sensitivity conjecture | What's new

  6. Pingback: Spectral proofs of theorems on the boolean hypercube | Anurag's Math Blog

  7. Pingback: Huangs’ Breakthrough, Cvetković’s Bound, Godsil’s Question, and Sinkovic’s Answer | Ratio Bound – A Combinatorics Blog

  8. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – Digitado

  9. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – 365 | Todas las noticias

  10. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit | cursovt

  11. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit - SonidoRD.com : SonidoRD.com

  12. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – Tribuna Liberal

  13. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit - PRESS.international

  14. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – Gacetalibre

  15. 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.

  16. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit – El Loco de la Colilla

  17. Pingback: Resuelto un famoso problema matemático en dos páginas condensadas en un tuit | KeepReading

  18. Pingback: Amazing breakthrough in theory of computation | Aquazorcarson's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s