敏感度猜想

对于任意布尔函数 $f : \{0, 1\}^n \to \{0, 1\}$，其敏感度 $s(f)$ 与块敏感度 $bs(f)$ 之间存在多项式关系；具体而言，对绝对常数 $C, c > 0$ 有 $bs(f) \le C \cdot s(f)^c$（事实上成立 $\deg(f) \le s(f)^2$，其中 $\deg(f)$ 为 $f$ 的实多项式次数）。

2019年7月，黄皓证明了 $n$ 维超立方体 $Q_n$ 的任意含 $2^{n-1} + 1$ 个顶点的导出子图 $H$ 的最大度满足 $\Delta(H) \ge \sqrt{n}$。黄皓递归构造了 $Q_n$ 的一个 $2^n \times 2^n$ 带符号邻接矩阵 $A_n$ 使得 $A_n^2 = n I_{2^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$。