解法：黄皓用带符号超立方体邻接矩阵证明敏感度猜想(2019年)

第 7/7 步：闭合逻辑:敏感度猜想得以解决

通俗地说

另一个由其他学者早先证明的要素完成了整个工作:块敏感度 $bs(f)$ 从不会比 $\deg(f)$ 大太多。把这一事实与黄皓的新界 $s(f) \ge \sqrt{\deg(f)}$ 连接起来,就得到 $bs(f)$ 与 $s(f)$ 之间直接的多项式关系,正是尼桑与塞格迪1992年所提问题的答案。

bs(f) \le s(f)^4

详细分析

尼桑与塞格迪(1992年)早已在相差一个常数因子的意义下证明了 $bs(f) \le \deg(f)^2$ ,后来塔尔(2013年)将其精确化为恰好 $bs(f) \le \deg(f)^2$ 。将第6步的定理1.4平方得到 $\deg(f) \le s(f)^2$ ,代入塔尔的界即得对每个布尔函数 $f$ 都有 $bs(f) \le s(f)^4$ 。这正是敏感度猜想所要求的多项式关系(带有明确常数 $C=4$ ),于是黄皓这个简短的谱论证——仅由一个巧妙的矩阵、一条经典的特征值交错定理和一个初等的行和估计构成——解决了一个近三十年来始终无法攻克的问题。

本步骤中的术语

块敏感度 $bs(f)$: 敏感度的一种放松:两两不相交的坐标块中,每一块单独翻转都能改变 $f$ 在某个输入处取值的最大块数。