Today’s arXived amazing paper by Hao Huang
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
Abstract: In this paper, we show that every -vertex induced subgraph of the -dimensional cube graph has maximum degree at least . 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 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.”