Today’s arXived amazing paper by Hao Huang’s
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 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.