感度予想（Sensitivity conjecture）

任意のブール関数 $f : \{0, 1\}^n \to \{0, 1\}$ に対して、感度 $s(f)$ とブロック感度 $bs(f)$ は多項式関係にある。具体的には絶対定数 $C, c > 0$ に対して $bs(f) \le C \cdot s(f)^c$ が成り立つ（実際には $f$ の実多項式次数 $\deg(f)$ に対して $\deg(f) \le s(f)^2$ が成立する）。

2019年7月、ハオ・ホアン（黄皓）は $n$ 次元超立方体 $Q_n$ の $2^{n-1} + 1$ 頂点からなる任意の誘導部分グラフ $H$ の最大次数が $\Delta(H) \ge \sqrt{n}$ であることを証明した。ホアンは $A_n^2 = n I_{2^n}$ を満たす $Q_n$ の $2^n \times 2^n$ 符号付き隣接行列 $A_n$ を帰納的に構成し、その固有値が重複度 $2^{n-1}$ の $\pm\sqrt{n}$ であることを用いた。コーシーの固有値交錯定理により、$A_n$ の任意の $(2^{n-1} + 1) \times (2^{n-1} + 1)$ 主小行列の最大固有値は少なくとも $\sqrt{n}$ となり、$\Delta(H) \ge \sqrt{n}$ が従う。ゴツマン・リニアルの同値性（1992年）とタルの評価（2013年）により、直ちに $\deg(f) \le s(f)^2$ および $bs(f) \le s(f)^4$ が導かれた。