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

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)]！

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

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

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

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

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

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

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 computer science," he says.