30年难题，两页纸证明！这位华人数学家攻克“布尔函数灵敏度”问题

会员服务 ·

30年难题，两页纸证明！这位华人数学家攻克“布尔函数灵敏度”问题

2019 年 7 月 28 日 新智元

新智元推荐

来源：大数据文摘(ID：BigDataDigest)

作者：文摘菌编译：宁静、易琬玉

整理编辑：张佳

【新智元导读】1992年，布尔函数敏感度猜想被提出。这成为了理论计算机科学近三十年来最重要的开放性问题之一。近日，来自Emory大学计算机与数学科学系的华人教授黄皓，用两页纸轻松证明了困扰理论计算机领域数十年的问题。

组成计算机的电路实际上是“与”“或”“非”逻辑电路的组合，多年来，计算机科学家已经开发出许多方法来测量给定布尔函数的复杂性。

科学家们发现，关于布尔函数的度量措施都适用于一个统一的框架，只有一个复杂性指标似乎不合适：“灵敏度”。1992年，耶路撒冷希伯来大学的Noam Nisan和现在罗格斯大学的Mario Szegedy 推测，“灵敏度”的确适合这一框架，但没人能证明这一点。“我想说，这可能是布尔函数研究中一个悬而未决的问题。”Servedio说。

现在，Emory大学的数学家黄皓用一个巧妙但简单的两页论证，证明了灵敏度猜想，这个论点关于立方体上的点的组合。

法国国家科学研究中心的Claire Mathieu在接受Skype采访时曾评价它为：“这只是一颗美丽的珍珠。”

黄皓是谁？这位华人科学家是怎么解开30年来一直困扰计算机科学家的问题呢？

华人数学家——黄皓

黄皓出生于汕头，这座海滨城市同时也是另一位著名数学家丘成桐的出生地。

十四岁的时候，黄皓就离开家乡奔赴广州华南师范大学附属中学就读。凭借优异的成绩，2003年黄皓被保送至北京大学攻读数学专业。在北大就读时，黄皓就在北京大学举办的首届“江泽涵”杯数学建模与计算机应用竞赛中获得三等奖，并出现在北大数学百年学生名录上。

2007年北大本科毕业后，黄皓在美国加州大学洛杉矶分校读博，师从国际著名数学家Benny Sudakov教授，并于2012年获得博士学位。

曾在2012-2014年受邀访问美国普林斯顿高等研究院，现担任美国艾默里大学数学系助理教授。主要研究领域包括极值组合、图论及计算机理论。

一次偶然与猜想的邂逅

2012年末，在受访美国普林斯顿高等研究院期间，黄先生在与数学家Michael Saks 共进午餐时听说了敏感性猜想，黄先生是博士后研究员。他立刻被这个猜想的简洁和优雅所吸引。“从那一刻开始，我开始沉迷于思考它。”他说。

黄将敏感性猜想添加到他感兴趣问题的“秘密列表”中，每当他学习新的数学工具时，他都会考虑它是否有帮助。“每次我发表新论文后，我都会回到这个问题，”他说。“当然，我会在一段时间后放弃，并解决一些更现实的问题。”

正如其他研究团体一样，黄知道，如果数学家可以证明一个关于不同维度立方体上的点集合比较容易陈述的猜想，那么灵敏度猜想就可以得到解决。从n 个0和1 的字符串到n维立方体上的点有一种自然的映射关系。

在2013年，黄开始认为理解这个问题的最佳途径可能是通过标准网络来表示网络，该矩阵跟踪哪些点连接，然后检查一组称为矩阵特征值的数字。五年来，他一直在重新审视这个想法，没有成功。

“但至少考虑它可以帮助我很快入睡。”他在Aaronson的博客文章中评论道。

然后在2018年，黄发现了使用一个有200年历史的称为Cauchy交错定理的数学，它将矩阵的特征值与子矩阵的特征值联系起来，使其成为研究立方体与立方体之间关系的完美工具。黄决定要求国家科学基金会拨款，以进一步探讨这一想法。

上个月，当他坐在马德里的一家酒店写下他的拨款建议时，他突然意识到他可以通过改变他的矩阵中某些数字的符号来推动这种方法的完成。通过这种方式，他能够证明在n维立方体中超过一半点的任何集合中，将存在某些与其他点的至少√n相关的点,灵敏度猜想也从这个结果中被证明。

“美丽的珍珠”

被法国科学家评为“美丽的珍珠”，这一猜想的证明思路是如何实现的呢？

先从“灵敏度”谈起，“灵敏度”是一种度量，捕获输入字符串中的信息如何影响输出位改变，换句话说，布尔函数的“灵敏度”跟踪翻转单个输入位改变输出位的可能性。

举个例子，想象一下，你正在填写银行贷款申请中的一系列Yes/No问题（问卷调查）。完成后，银行家将对您的结果进行评分，并告诉您是否有资格获得贷款。这个过程是一个布尔函数：你的答案是输入位，而银行家的决定是输出位。

如果你的申请被拒绝，你可能想知道你是否可以通过单一问题的选择而银行的预判结果，比如你口袋里面真的没有多少钱时，在收入超过50,000美元那一栏你打了勾，如果这个谎言会导致预判结果，计算机科学家说布尔函数对该特定位的值“敏感”。比方说，如果有七种不同的谎言，你可以说它们会分别翻转结果，那么对于你的贷款资料，布尔函数的灵敏度是7。

为了可视化计算机电路对位翻转错误的敏感程度，我们可以将其n个输入位表示为n维立方体的坐标，例如，四个两位字符串00,01,10和11对应于二维平面中正方形的四个角：（0,0）、（0,1）、（1,0）和（1,1）。同样，八个三位字符串对应于三维立方体的八个角，以此类推到更高的维度。反过来，布尔函数可以被认为是用两种不同颜色着色这些角的规则，如果最终输出为1则将立方体的一角标为蓝色，反之，则标为红色。