黄皓之后，计算机科学上帝Don Knuth仅用一页纸证明布尔函数敏感度猜想

2019 年 8 月 8 日 AI100

作者 | Freesia

编辑 | 夕颜

出品 | AI科技大本营（ID:rgznai100）

导读：近日，美国艾默里大学计算机与数学科学系教授黄皓（Hao Huang）用一篇短短 6 页的论文证明了布尔函数，引发了计算机和数学领域社区的广泛关注。不久之后，在这篇论文的启发下，计算机科学的上帝 Don Knuth 再次突破极限，仅用一页纸就证明了这个困扰理论计算机领域数十年的布尔函数敏感度猜想（其中半页证明还是笔记）。

一页纸证明布尔函数

7 月 28 日，Don Knuth 在讨论黄皓证明布尔函数的帖子下发声，表示自己仅用一页纸就做到了这件事，并附上了证明过程的文档： https://www.cs.stanford.edu/~knuth/papers/huang.pdf

他在文档中 Don Knuth 说道：黄皓最近运用组合学成功地解决了 30 年前由 Nisan 和 Szegedy 提出的布尔函数的敏感度猜想，并指出本证明使 Shalev Ben-David 在 7 月 3 日在 Scott Aaronson 博客上发表的想法具体化。

顺便说一句，如果其他人（像我一样）对柯西积分定理不熟悉或不习惯，这里有一个不使用该定理的证明版本：

设 S 是矩阵 A_n 的 sqrt（n）- 原点空间。S 的维数为 2 ^（n-1）。设 A_n 的大的主子矩阵为 B。我们希望降低其频谱范数（最大特征值）。这与使用范数 1 的向量 x 最大化相同。但是不难看出，对应于不在 B 中的行/列的索引上具有 0 项的超过单位向量 x 的最大值，此最大值与之相同。将 L 乘以所有向量在这些索引上具有 0 个项的子空间。此外，L 具有至少 2 ^（n-1）+1 个维度，因为 B 至少使用这些数量的行/列。因此，L 与 S 的交点必须具有至少 1 个维数。可得出，在 L 和 S 中都存在单位向量 x，意味着它对应于不在 B 中的行/列，但是sqrt （n） - A_n 的本征向量中有 0 项。和预期一样，这达到了 B 的谱范数上 sqrt（n）的下界。

Don Knuth——计算机科学的上帝

（图源：斯坦福大学官网）

这次，用一页纸证明了布尔函数敏感度猜想的大师，正是被誉为计算机科学上帝的 Don Knuth 教授，现为斯坦福大学计算机系荣誉退休教授。

Knuth 于 1938 年 1 月 10 日生于威斯康辛州密歇根湖畔的密尔沃基(Milwaukee)。“人工智能之父”、斩获诺贝尔奖和图灵奖的获得者西蒙(H．A．Simon)也在这里出生。

Knuth 是算法和程序设计技术的先驱者，创造了算法分析的领域，在数个理论计算机科学的分支做出基石一般的贡献，发表了多部具广泛影响的论文和著作。在工作之余，他用了十年时间发明了计算机排版系统 TEX 和 METAFONT。

少年时期的 Knuth 便显示出在数理上的天赋，年纪轻轻便已编著了堪称计算机科学理论与技术的经典巨著《计算机程序设计的艺术》，并于 36 岁凭借《计算机程序设计艺术》的前 3 卷（计划 7 卷）拿到了 1974 年度的图灵奖。该书还被《美国科学家》杂志列为 20 世纪最重要的 12 本物理科学类专著之一，与爱因斯坦《相对论》、狄拉克《量子力学》、理查·费曼《量子电动力学》等经典比肩而立。《计算机程序设计的艺术》系列计划出七卷，至今为止已经出版了四卷：第一卷《基本算法》于 1968 年出版，第二卷《半数字化算法》于 1969 年出版，第三卷《排序与搜索》于 1973 年出版，第四卷《组合算法》于 2008 年出版。

黄皓证明布尔函数敏感度猜想回顾

在这之前，美国艾默里大学计算机与数学科学系教授黄皓（Hao Huang）用一篇短短 6 页的论文证明了困扰理论计算机领域数十年的布尔函数敏感度猜想，引发了计算机和数学领域社区的广泛关注。

布尔函数在研究密码算法和密码技术上应用甚广，其应用领域包括流密码与分组密码，还有对称和非对称密码。在数学中，定义域{1,2,3,... } 的这种函数通常叫做二进制序列，通过限制到 { 1,2,3,...,n }，布尔函数是指编码长度为 n 的序列的自然的方法。通常是如下形式的函数：F(b1,b2,...,bn)，布尔变量bi带有 n 个来自两元素布尔代数 {0,1} ，F的取值也在 {0,1} 中，有 2^{2^n} 个布尔函数。

作为理论计算机科学中近三十年来最重要、最令人困惑的开放性问题之一，布尔函数引得无数计算机科学或数学领域的学者教授摩拳擦掌。而“敏感度”是一种度量，捕获输入字符串中的信息如何影响输出位改变，换句话说，布尔函数的“敏感度”是跟踪翻转单个输入位改变输出位的可能性。

我们回顾一下黄皓是如何证明布尔函数的敏感度的：

早在 1992 年，现任新泽西理工计算机学院院长 Craig Gotsman 和希伯来大学计算机科学教授 Nati Linial 便找出了证明敏感度猜想的思路：通过回答一个有关不同维度立方体的问题将敏感度猜想大大简化，如果将超过一半的立方体尖角同时涂为红色，是否总是有一些红色点是与其他红色点相连接？

起初黄皓认为理解这一问题的最佳路径是使用矩阵表示网络并检测矩阵特征值。因此，从 2013 年到 2018 年，他一直试验这个思路，但都没有成功。

2018 年，黄皓决定使用柯西交错定理（Cauchy interlace theorem），该定理将矩阵特征值和子矩阵特征值关联起来，因此成为研究立方体及其尖角子集的完美工具。经过一段时间的研究后，他发现可以通过简单地改变矩阵中一些数字的符号来直接解决问题。通过这种方式，他证明了在 n 维立方体中任何超过一半点的集合中，会有一些点和其他点有至少

个连接，敏感度猜想问题也由此得以证明。

(*本文为 AI科技大本营原创文章，转载请联系微信 1092722531)

社群福利

扫码添加小助手，回复：大会，加入2019 AI开发者大会福利群，每周一、三、五更新技术福利，还有不定期的抽奖活动~

◆

精彩推荐

◆

60+技术大咖与你相约 2019 AI ProCon！大会早鸟票已售罄，优惠票速抢进行中......2019 AI开发者大会将于9月6日-7日在北京举行，这一届AI开发者大会有哪些亮点？一线公司的大牛们都在关注什么？AI行业的风向是什么？2019 AI开发者大会，倾听大牛分享，聚焦技术实践，和万千开发者共成长。

推荐阅读