The sensitivity conjecture

Solved in 2019 by Hao Huang.

The sensitivity of a Boolean function at an input is the number of single-bit flips that change its value, and it is one of many ways to measure how complex a Boolean function is. In 1992 Nisan and Szegedy asked whether sensitivity is polynomially related to the other standard measures, and Gotsman and Linial reduced the question to the hypercube statement above. Before 2019 the best lower bound for that statement was logarithmic in $n$, due to Chung, Füredi, Graham and Seymour in 1988. In July 2019 Hao Huang gave a very short proof. He signed the edges of the hypercube so that the signed adjacency matrix squares to $n$ times the identity, which forces half its eigenvalues to equal $\sqrt{n}$, and then used eigenvalue interlacing. The bound is best possible, it gives $s(f)\ge \sqrt{\mathrm{deg}(f)}$, and the paper appeared in the Annals of Mathematics in 2019.

References

• Sensitivity conjecture (Wikipedia)
• H. Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture (arXiv:1907.00847)