Sensitivity conjecture

For every Boolean function $f : \{0, 1\}^n \to \{0, 1\}$, the sensitivity $s(f)$ and the block sensitivity $bs(f)$ are polynomially related; specifically, $bs(f) \le C \cdot s(f)^c$ for absolute constants $C, c > 0$ (and in fact $\deg(f) \le s(f)^2$, where $\deg(f)$ is the real polynomial degree of $f$).

In July 2019, Hao Huang proved that every induced subgraph $H$ of the $n$-dimensional hypercube $Q_n$ with $2^{n-1} + 1$ vertices has maximum degree $\Delta(H) \ge \sqrt{n}$. Huang inductively constructed a $2^n \times 2^n$ signed adjacency matrix $A_n$ of $Q_n$ satisfying $A_n^2 = n I_{2^n}$, whose eigenvalues are $\pm\sqrt{n}$ each with multiplicity $2^{n-1}$. By Cauchy's interlace theorem, any $(2^{n-1} + 1) \times (2^{n-1} + 1)$ principal submatrix of $A_n$ has largest eigenvalue at least $\sqrt{n}$, forcing $\Delta(H) \ge \sqrt{n}$. Via the Gotsman–Linial equivalence (1992) and Tal's bound (2013), this immediately implies $\deg(f) \le s(f)^2$ and $bs(f) \le s(f)^4$.