Amazing: Hao Huang Proved the Sensitivity Conjecture!

Today’s arXived amazing paper by Hao Huang’s

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 important relation between the two problems  by Gotsman and Linial. It uses beautifully 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 solve it see this post on Aaronson’s Shtetl Optimized (SO).  See also this post on GLL. Updates: 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⩽π!)

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.

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

5 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

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