黄皓解决了布尔函数的敏感度猜想

Mathematician to present a proof of the Sensitivity Conjecture

一位华人学者刚刚解决了敏感度猜想Sensitivity Conjecture，它是理论计算机科学中近三十年来最重要，最令人困惑的开放性问题之一。

鉴于之前评论里有人吐槽说，类似文章全是泛泛而谈的一般科普，核心内容一带而过，就丢出一个链接，所以下面详细说一下敏感度猜想——在汉语网络环境里，相关信息貌似挺少见的。

敏感度猜想，涉及布尔型数据，以及其上的函数关系。

• 假设x是一个n维数组，其中每个分量都是取值于0或1的布尔数。

• 假设函数f:{0，1}^n—>{0，1}，亦即定义域是n维数组，同时每个分量都是布尔数；取值也是布尔数。

• 翻转x第i个分量的值（就是数组中第i个值如果是0，则变成1；是1，则变成0），得到x_i，如果f（x_i）≠f（x），就称f对x在第i个分量处敏感。

• f对x可能在若干分量处都敏感，记敏感分量的数目为s（f，x）。

• 当x取遍n维布尔数组后，记s（f，x）的最大值为s（f）。

  到此为止，就得到了布尔函数敏感性的定义，但是，猜想本身用到的是布尔函数的块敏感性！

  简单说一下，就是上面步骤③里，x_i的角标不再是i，而是集合A，A本身是集合{1,2，……，n}的某个子集。对特定的想，相应的定义，把{1,2，……，n}分化成若干不想交子集，保证f对每个子集都是敏感的。必然有种方式使子集个数最多，子集个数记为相应的bs（f，x），进一步得到bs（f）。

  1994年，数学家Noam Nisan和Mario Szegedy提出了敏感度猜想Sensitivity Conjecture：

  存在一个多项式P，对所有的布尔函数f，都成立 bs（f）≤P[s（f）]！

  在计算机科学和数理逻辑，乃至代数学里，布尔函数无疑是是否重要的研究对象。同时，我们知道，布尔函数有许多复杂性测度，并且几乎所有这些测度——包括决策树复杂性，证书复杂性，随机查询复杂度和其它许许多多——已知都是多项式相关的。

  最新证明的提出者、埃默里大学的数学助理教授黄皓向我们解释猜想的价值和意义：“在数学中，布尔函数是最基本的离散主题之一——就像数字，图形或几何形状一样。但是，其它测度都是多项式相关的，而如果猜想为真，则敏感度也是如此，否则的话，它就是很反常的量。”

  “自2012年以来，我一直尝试攻克这一猜想。”Huang在接受phys.org采访时说，“但是直到大约一周前，我才捕捉到关键思想。我终于找到了那把正确的钥匙。”

  7月15日至19日，将在瑞士苏黎世召开随机结构和算法的国际会议。黄皓在会议上正式发布证明。想要了解详情的朋友可以点击此处阅读、下载论文的预印本。

  在论文里，黄皓先证明n维超立方图的生成子图的相关命题，将猜想作为命题的直接推论。其精巧思路和简单明了的过程，在社交媒体上赢得了计算机科学家和数学家的一片赞誉。

  黄皓开发出了一种代数方法。“我希望这种方法也有可能应用到对计算机科学的发展至关重要的其他组合和复杂性问题上。”

Mathematician to present a proof of the Sensitivity Conjecture

by Carol Clark,  Emory University                                                                              

Emory mathematician Hao Huang says that the algebraic tool that he developed to tackle the problem "might also have some potential to be applied to other combinatorial and complexity problems important to computer science.” Credit：Emory University

The Sensitivity Conjecture has stood as one of the most important, and baffling, open problems in theoretical computer science for nearly three decades. It appears to have finally met its match through work by Hao Huang, an assistant professor of mathematics at Emory University.

Huang will present a proof of the Sensitivity Conjecture during the International Conference on Random Structures and Algorithms, set for Zurich, Switzerland, July 15 to 19.

"I've been attacking this problem off and on since 2012," Huang says, "but the key idea emerged for me just about a week ago. I finally identified the right tool to solve it."

Huang posted the proof on his home page and it soon generated buzz among mathematicians and computer scientists on social media, who have praised its remarkable conciseness and simplicity.

The Sensitivity Conjecture relates to boolean data, which maps information into a true-false, or 1-0 binary. Boolean functions play an important role in complexity theory, as well in the design of circuits and chips for digital computers.

"In mathematics, a boolean function is one of the most basic discrete subjects—just like numbers, graphs or geometric shapes," Huang explains.

There are many complexity measures of a boolean function, and almost all of them—including the decision-tree complexity, the certificate complexity, the randomized query complexity and many others—are known to be polynomially related. However, there is one unknown case, the so-called sensitivity of a boolean function, which measures how sensitive the function is when changing one input at a time.

In 1994, mathematicians Noam Nisan and Mario Szegedy proposed the Sensitivity Conjecture concerning this unknown case.

"Their conjecture says the sensitivity of a boolean function is also polynomially related to the other measures," Huang says. "If true, then it would cease to be an outlier and it would join the rest of them."

Huang developed an algebraic method for proving the conjecture. "I hope this method might also have some potential to be applied to other combinatorial and complexity problems important to computerscience," he says.

“珍珠般的美丽”：华人年轻数学家的研究
邸利会

 
中文常常把科学家描写的天才而古板，有时还奇葩。今天我们见识生活事业顺利、年轻充满活力的杰出青年科学家。他虽然是数学家，但不古板而乐观开朗。在兼顾现实世界需要他发表文章的同时，六年间坚持悄悄地研究一个横跨组合与计算机理论的一个三十年悬而未决的难题，终于一举攻克之，解决方案简单而优美，为同行交口称赞。

困扰理论计算机界30年的猜想，被他一页半纸解决了。

7月1日，一篇论文出现在arXiv上，与通常动辄几十上百页的证明不同，这篇论文连参考文献在内不到6页，实际上整个的证明不到两页。

文章的作者是埃默里（Emory）大学数学系助理教授黄皓，他2007年曾本科毕业于北京大学。

“证明非常精美，尤为让人欣赏的是它使用工具初等，而且整个证明只有两页（核心其实不到一页）。大家显然都错过了他的这条路。证明中主要用的构造和引理贴合的恰到好处。整个证明也许是长期思索和尝试下的精妙发现，让人赞叹。” 在看到论文后，腾讯杰出科学家张胜誉告诉“赛先生”。

黄皓所解决的猜想名为“敏感性猜想”（Sensitivity Conjecture），由耶路撒冷希伯来大学的Noam Nisan和现在罗格斯大学的Mario Szegedy在1992年所提出，是具体复杂性理论（concrete complexity）中一个广为人知的猜想。

“我不能想象甚至上帝可以找得到比这更简单对敏感性猜测的证明。” 德克萨斯大学奥斯汀分校的理论计算机科学家Scott Aaronson在发给Quanta杂志的邮件中说。“它是组合论和理论计算机科学中最令人沮丧和难堪的问题之一”，“试图解决它而失败的人们就是离散数学和理论计算机科学的名人堂” Aaronson在博客里写道。

确实，过去的近30年，很多人都尝试证明或者证否这一猜测，相关的文献也累计了五六十篇，但都没有成功。

“黄皓的证明简单而优雅，以至于人们可能难以找到更好的一个证明！这个问题本身某种程度是孤立于其它课题的，不过，它确实是很知名，之前的办法都没拿下它。很多世界领先的研究者都曾尝试但都失败了。” 爱丁堡大学信息学学院讲师郭珩在邮件中回复“赛先生”。

没人想到，这个猜想会以这样简洁而优雅的方式得到证明。法国科学研究中心的数学家和计算机科学家Claire Mathieu感叹：“这真漂亮，像是一颗宝贵的珍珠”。

“不合群”的敏感度？
“敏感性猜想”涉及到大概有200年的历史的布尔函数。这个函数在复杂性理论、电子电路设计和芯片设计中都很基本，在密码学里也有重要的角色。函数并不复杂，输入是一段由0和1组成的比特串，输出是0或者1。

为了研究布尔函数，人们很早定义了十几个关于其复杂性的度量，加上它们的变体和一些后续的新的度量，一共有几十个，敏感度也属于其中的一个。

你可以这样理解敏感度：对于一个给定的n位比特串，每一位翻转一下（由1变成0或者由0变成1），如果布尔函数的值也发生翻转，那这个位就算一次，最后可以得到有多少个位翻转会改变函数值。这个叫做局部的敏感度。整体的敏感度就是对于所有的n位比特串，取最大的一个局部敏感度。

对定义在n位比特串上的布尔函数，包括敏感度在内的这几十个度量之间的关系慢慢得到了越来越好的理解。有趣的是，其中有一大类从不同角度定义的度量都“差不多大小”，即每个都不超过另一个的多项式（比如平方或者三次方），属于一个大家庭。

当然，人们也知道有些度量不属于这个大家庭，但是有一个显著的例外，就是敏感度这个很基本的度量——大家不知道它的位置，虽然一直猜测它是属于这个大家庭的，但没人能给出证明。

“我的工作就是证明了敏感度也和别的一样都是在一个范畴之内。” 黄皓告诉“赛先生”。

最早接触到这个猜测是在2012年末，那时黄皓在普林斯顿高等研究院做博士后。在和数学家Michael Saks的一次午餐中，他听说了这一猜测，自此念念不忘。

“当时组里大部分人是做理论计算机方向，他们会给我讲他们感兴趣的理论计算机里面比较数学化的问题。” 黄皓回忆说。

之后的黄皓一直对其情有独钟，每发表一篇文章后，他又会去想这个问题。想不出来又去做其他更现实的问题，之后再回去继续想这一问题——也许有一天柳暗花明呢？

N维超方体
同样是在1992年，现任新泽西理工学院的Craig Gotsman和希伯来大学的Nati Linial发现，证明灵敏度猜想的问题和一个图论的问题是等价的。

“敏感性猜想本身的表述是关于理论计算机算法复杂度理论中研究的核心对象布尔函数（Boolean function），但是和理论计算机中的很多问题类似，这个猜想可以规约到了数学的一个分支——组合图论上的问题。” 中国科学技术大学数学系马杰教授说。

而图论也是黄皓感兴趣的方向。

图论的研究在理论和实际应用都有重要意义。我们可以把很多实际生活中的事物看成是图论学中的数学研究对象——图（Graph），比如可以把微信中所有的用户关系抽象成一个图，其中每个用户是图中的一个节点，两两之间的好友关系看成是图中两个节点中的一条边。

Gotsman和Linial证明，敏感度猜想事实上等价于在N维超方体（hypercube）这一重要图类上证明这样一个数学命题：n维超方体中任意超过一半节点的子结构中都含一个节点，它至少和“很多”其它节点有边相邻；这里“很多”用严格的数学言语讲的话，就是说要至少大于等于关于n的一个多项式函数。

这样的一个难懂的问题在转成图的问题后，解释起来也变的比较容易。

你可以想象有一个N维超方体，顶点的坐标是由长度为n的由0和1组成的比特串。如果n＝2，那就有四个顶点，坐标分别为00，01，10，11，如果两个比特串只有一位不同，就连一条边，比如00和01，00和10，10和11，01和11都连着边，但00和11，01和10不连着边。你可以自行想象下三维的情形。

这种图有一个性质是，如果取一半那么多的顶点，这些顶点可以两两之间没有边，比如二维的情形，取00和11，或者取10和01，它们之间没有边；三维的情形下，你可以取000，110，101和011这四个顶点，也是一半的顶点，它们之间没有边。

“我证明的结果是说，如果你取一半多一个的点的话，必然存在其中的某一个点，至少和√n个你选择的点相邻，从这个是可以推出多项式关系。” 黄皓解释说。

正如前文所说，这个多项式关系就是敏感度和其它度量相比，一个不太大，另一个也不会太大，另一不太小，另一个也不会太小。

提到解决问题的关键，黄皓说，他用到的代数的方法，不是那种传统的组合的方法。“有两三个代数的方法，大家都比较熟悉，难度主要是想到怎样把这几样东西组合起来，不是说每样东西有多特别。” 他说。

就在上个月，当他坐在马德里的一家酒店写项目申请书时，他突然意识到，几样东西可以拼在一起了。很快，他就完成了这个证明，如此简单而明快的证明。

“在黄皓的极为精巧和优美证明中，他首先注意到超方体这个问题可以进一步转换成一个关于矩阵的极值问题，然后人们就可以借助于数学中的代数工具去做更为精细的分析。这是我见过的最为神奇美妙的数学证明之一。从我的观点看，这个证明中最为美妙的地方在于处理矩阵的绝妙技巧以及背后的深邃数学思想；我想这是一个将来一定会写进教科书、在组合数学和理论计算机界具有持续影响力的数学证明。” 马杰说。

马杰也是黄皓多年的合作者，在他看来，黄皓是一个非常独立的、有自己学术追求的杰出的青年数学家，和他的合作过程中令人非常愉悦，往往能学到很多有意义的数学想法和思考。

“他的这个结果无疑是近些年来整个理论计算机领域的重大创新之一，为华人数学界和计算机学界挣得了巨大的荣誉；非常为他感到骄傲” 马杰说。

诚如张胜誉所猜测的，“整个证明也许是长期思索和尝试下的精妙发现”，的确，从2012年第一次听说这个猜想算起，黄皓的思考持续了6年多，期间他还做着其它的问题。

对黄皓来说，和做理论计算机的人交流也是蛮有意思的事情，这两个领域的人有可能再说同一件事，但却在用完全不同的语言来讲。提到将来会不会解决更多的理论计算机难题，黄皓说，还是要看机缘——

“都没有非要做什么，不要做什么，可能看当时的心情，或者刚好对什么类型的问题感兴趣，就很难说，计划好接下去你要干什么。”

当法国科学家Claire Mathieu第一次看到论文时，她以为既然三十年人人知道而解决不了这一问题，那么答案恐怕是很长很复杂、或者很深，但一看黄皓的文章发现它简单到大家都能一次就理解。她说：“我预计今年秋天大家就会用它讲课，也许是每一堂硕士水平的组合课都会讲。”

今年秋天，你或许就会在课堂上听到这个美妙的证明了。

参考资料
[1] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, arXiv:1907.00847
[2] Erica Klarreich, Decades-Old Computer Science Conjecture Solved in Two Pages, https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/