Sensitivity conjecture

Solved, 2019Combinatorics and discrete mathematicsApplied and computational mathematics

Statement

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$ .

Prior to Huang's theorem, decision-tree depth $D(f)$ , certificate complexity $C(f)$ , block sensitivity $bs(f)$ , polynomial degree $\deg(f)$ , and quantum query complexity $Q(f)$ were all known to be polynomially equivalent, with sensitivity $s(f)$ being the sole holdout. While $\deg(f) \le s(f)^2$ is tight, the optimal exponent between $bs(f)$ and $s(f)$ —known to lie between $2$ (Rubinstein's quadratic separation) and $4$ (Huang + Tal)—remains open.

References

Hao Huang (2019). Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture · DOI:10.4007/annals.2019.190.3.6 · arXiv:1907.00847
Craig Gotsman, Nathan Linial (1992). The equivalence of two problems on the cube · DOI:10.1016/0097-3165(92)90060-8

History of the problem

1988Fan Chung, Zoltán Füredi, Ronald Graham, and Paul Seymour prove that any induced subgraph of $Q_n$ on $2^{n-1} + 1$ vertices has maximum degree at least $(\frac{1}{2} - o(1)) \log_2 n$ , and construct an example achieving $\lceil \sqrt{n} \rceil$ .
1992Noam Nisan and Mario Szegedy pose the sensitivity conjecture $bs(f) \le \mathrm{poly}(s(f))$ ; Craig Gotsman and Nathan Linial prove its equivalence to a polynomial degree bound on $(2^{n-1} + 1)$ -vertex subgraphs of $Q_n$ .
2019Hao Huang proves $\Delta(H) \ge \sqrt{n}$ via signed adjacency matrices and Cauchy's interlace theorem, proving $\deg(f) \le s(f)^2$ and resolving the sensitivity conjecture.