近日，数学学院03级本科院友黄皓博士发文证明了“敏感度猜想”，此事引起学界的广泛关注。其论文的核心内容仅占两页纸，许多专家认为，黄皓博士关于“敏感度猜想”的证明过程简洁巧妙，为布尔函数研究中的其他问题提供了工具。国际上相关领域的权威人士对此给予了很高的评价。

敏感度猜想（sensitivityconjecture）是计算机科学和组合数学中最著名的未解决问题之一，最早于1989年由NoamNisan和MarioSzegedy提出。

考虑一个n元的布尔函数f:{0,1}^n->{0,1}。这样的一个函数可以理解成n个人每人戴上红色或蓝色帽子的所有情况。对每种情况，f给出两个答案之一，例如高兴或是沮丧。

对任何一种情况x，如果将这种情况中某人的帽子颜色改变会导致f的结果改变，我们称这个人在x中是敏感的。我们定义x的敏感度为该情况中敏感的人数。函数f的敏感度s(f)定义为所有情况的敏感度的最大值。

对一种情况x，我们还可以定义另一种块状的敏感度：如果有一组人，在x中同时改变这组人帽子的颜色，会改变f的值，我们称这组人在x中是敏感的。我们想在所有情况中找到一种，使得其中可以找出尽可能多的敏感组，但每个人不能同时属于两组，这个最大值称为f的块状敏感度bs(f)。

为了测试你的理解，你是不是看到bs(f)至少不比s(f)小？

在计算理论中，可以证明bs(f)和许多其它关于f的复杂度的度量相互之间有多项式的关系，例如：f的决策树复杂度、f作为多项式的度数、随机查询复杂度、量子查询复杂度、等灯等灯。

但是，s(f)呢？这个当我们谈起敏感度的时候觉得最为自然的定义，它和其它度量的关系是什么样的呢？这就是著名的敏感度猜想：

存在一个常数c，使得bs(f)≤s(f)^c.

也就是说，s(f)和上面所有的度量都有多项式的关联关系。

黄皓，2003年至2007年就读于北京大学数学学院并获理学学士学位，2012年于UCLA获得博士学位，先后在IAS、Rutgers的DIMACS中心、以及明尼苏达大学做过博士后，现任Emory大学数学与计算机系助理教授。其研究兴趣包括极值组合学、概率/代数方法、谱图理论、结构图理论和理论计算机科学等。

论文详情请点击https://arxiv.org/abs/1907.00847查看。

本文部分内容转载自https://mp.weixin.qq.com/s/6vZrH1fMi_JRY74GU0Z9MQ