华人学者解开计算机领域30年难题：布尔函数敏感度猜想
整理 | 郭芮
来源 | CSDN（ID：CSDNnews）
1992年，布尔函数敏感度猜想（Boolean Sensitivity）被提出，这成为了理论计算机科学近三十年来最重要、最令人困惑的开放性问题之一。而近日，来自Emory大学计算机与数学科学系的华人教授黄皓，用两页纸证明了困扰理论计算机领域数十年的问题。
困扰科学界 30 年的难题
多年来，计算机科学家已经开发出许多方法来测量给定布尔函数的复杂性。研究发现，关于布尔函数复杂性的度量措施都适用于一个统一的框架，但有一个复杂性指标似乎并不适用——“灵敏度”。灵敏度（sensitivity conjecture）是一种衡量布尔函数复杂度的方法，它被定义为导致布尔函数翻转的最大比特数，通过捕获输入字符串中的信息来影响输出位的改变。换句话说，布尔函数的“灵敏度”跟踪翻转单个输入位改变输出位的可能性。
1992年，耶路撒冷希伯来大学的Noam Nisan和现在罗格斯大学的Mario Szegedy 推测表示，“灵敏度”同样是适合统一框架的，但没有人能证明这一点，这也成为了布尔函数研究中一个悬而未决的问题。
灵敏度猜想的证明具有很大的实践意义，主要涉及计算机电路的基础构造块结构，包括：医生可以在达到诊断之前尽可能少地为患者发送测试；机器学习专家可以通过算法在分类之前尽可能少地检查对象的特征；银行家可以向老板展示尽量少的答案以证明他们已做出正确的贷款决策；甚至还涉及量子物理学版本的查询复杂性，弄清楚该测量与其他复杂性测量的关系可以帮助研究人员理解量子算法的局限性......
外媒Quantamagazine就此问题举例说：如果你向银行申请贷款，那么就需要填一系列答案为是或否的问题，银行再根据你的答案进行评分做出决定——这个过程就是一个布尔函数，你的答案就是输入比特，银行的决定就是输出比特。如果你改变某个问题的答案会导致结果翻转，这个比特/答案就被定义为敏感了，如果有7个问题任意一个翻转会导致结果翻转，那么其敏感度就是7。
在这二十多年中，该猜想难倒了许多优秀的计算机科学家。而现在，Emory大学的数学家黄皓用一个巧妙但简单的两页论证，证明了灵敏度猜想。
华人科学家黄皓用7年时间破解
本月初，一篇仅有6页的论文悄悄登上了arXiv，引起了学术界的轰动。一位名叫黄皓（Hao Huang）的华人科学家解开了30年来一直困扰计算机科学家的问题，论文长度仅有6页，其核心证明内容只有2页。
黄皓（Hao Huang），图源：Quantamagazine
黄皓出生于汕头，十四岁时离开家乡奔赴广州华南师范大学附属中学就读，凭借优异的成绩于2003年被保送至北京大学攻读数学专业。2007年北大本科毕业后，黄皓在美国加州大学洛杉矶分校（UCLA）读博，师从国际著名数学家Benny Sudakov教授，并于2012年获得博士学位。2012-2014年受邀访问普林斯顿高等研究院，现担任美国艾默里大学数学系助理教授。其主要研究领域包括极值组合、图论及理论计算机，已经在JCTB、JCTA、Combinatorica、SIAM J. Discrete Math等国际著名期刊上发表及接受发表论文20余篇。
2012年末，在受访美国普林斯顿高等研究院期间，黄皓在与数学家Michael Saks共进午餐时听说了敏感性猜想，他立刻被这个猜想的简洁和优雅所吸引。“每次我发表新论文后，我都会回到这个问题，”他说。“当然，我会在一段时间后放弃，并解决一些更现实的问题。”
在2013年，黄皓开始认为理解这个问题的最佳途径可能是通过标准网络来表示网络，该矩阵跟踪哪些点连接，然后检查一组称为矩阵特征值的数字。五年来，他一直在重新审视这个想法，但一直没有成功。2018年，黄皓发现了使用一个有200年历史的称为Cauchy交错定理的数学，它将矩阵的特征值与子矩阵的特征值联系起来，使其成为研究立方体与立方体之间关系的完美工具。
上个月，他突然意识到他可以通过改变他的矩阵中某些数字的符号来推动这种方法的完成。通过这种方式，他能够证明在n维立方体中超过一半点的任何集合中，将存在某些与其他点相关的点，灵敏度猜想也从这个结果中被证明。
图源：Quantamagazine
这个存在了30年的难题，最终证明是如此简洁甚至可以用一条推文概况。
图源Twitter：CMU计算机科学系教授Ryan O'Donnell
而为了解决这个问题，黄皓花费了7年时间来思考。
Quantamagazine最后写到，“黄皓的研究结果超过了证明灵敏度猜想所必需的结果，这种发现应该会产生关于复杂性度量的新见解。”哥伦比亚大学计算机科学教授Rocco Servedio也表示，“它充实了我们的工具库，让我们可以试图回答布尔函数分析中的其他问题”，“我认为在这一证明推出以后，很多人终于能睡得着觉了。”
参考链接：
https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/
https://news.cnblogs.com/n/628833
https://new.qq.com/omn/20190727/20190727A0B1GX00.html
(*本文为 AI科技大本营转载文章，转载请联系作者)
◆
精彩推荐
◆
60+技术大咖与你相约 2019 AI ProCon！大会早鸟票已售罄，优惠票速抢进行中......2019 AI开发者大会将于9月6日-7日在北京举行，这一届AI开发者大会有哪些亮点？一线公司的大牛们都在关注什么？AI行业的风向是什么？2019 AI开发者大会，倾听大牛分享，聚焦技术实践，和万千开发者共成长。
推荐阅读
超全！深度学习在计算机视觉领域的应用一览
数十篇推荐系统论文被批无法复现：源码、数据集均缺失，性能难达预期
SpanBERT：提出基于分词的预训练模型，多项任务性能超越现有模型！
真实揭秘 90 后程序员奔三准备：有人学金融投资，有人想当全栈工程师！
Python之父新发文，将替换现有解析器
乘势而起，走进2019年风口“边缘计算”
天网恢恢！又一名暗网比特币洗钱者被抓了
你点的每个“在看”，我都认真当成了喜欢相关文章：
从1.5K到18K 一个程序员的5年成长之路(二)
这一切都来自于心态CSDN：从开始学习，到学有所成和找工作，再到工作中遇到各种困难，然后获得突破，在整个过程中，能总结下你心态都有哪些变化？是用运用什么方法或方式进行调整？雷果国&a…
设计模式之享元模式(Flyweight)摘录
23种GOF设计模式一般分为三大类：创建型模式、结构型模式、行为模式。 创建型模式抽象了实例化过程，它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类，而一个对象创建型模式将实例化委托给…
你想见的大神都来AI ProCon 2019了，优惠票限时抢购开启！
如今 AI 的发展真实地面临着诸多瓶颈、尽管很多智能助手已经可以执行很多任务，但距离真正的人机自然交互还需要很长时间；强人工智能也迟迟未出现，不知何时才能出现；现有的 AI 只能做好一件事，Alpha Go 只会下棋&#x…
qt练习11 鼠标,按键,滚轮事件学习
源代码: http://files.cnblogs.com/hnrainll/event.zip
windows server 2008 R2上安装MRTG指南
一、实验环境 参考教程：http://www.netmon.org/dummies.htm http://www.docin.com/p-158415185.html MRTG中文手册：http://bbs.chinaunix.net/thread-1344687-1-1.html http://www.enterastream.com/whitepapers/mrtg/mrtg-manual-cap9.html 1.硬件平台 …
设计模式之外观模式(Facade)摘录
23种GOF设计模式一般分为三大类：创建型模式、结构型模式、行为模式。 创建型模式抽象了实例化过程，它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类，而一个对象创建型模式将实例化委托给…
知识图谱公开课 | 详解事件抽取与事件图谱构建
现有知识图谱大多关注于以实体为核心的静态知识，缺乏对于以事件为核心的动态知识的刻画和构建。如何从非结构化文本中抽取结构化的事件知识已成为眼下热门研究课题。本次公开课中，我们邀请到了中科院自动化所模式识别国家重点实验室助理研究员陈玉博&…
实时显示系统时间
CTime time;CString m_time;void CtimeDlg::OnBnClickedButton1(){// TODO: 在此添加控件通知处理程序代码 SetTimer(1,1000,NULL);}void CtimeDlg::OnTimer(UINT_PTR nIDEvent){// TODO: 在此添加消息处理程序代码和/或调用默认值 timeCTime::GetCurrentTime(); …
安卓手机文件管理器：360°LES文件浏览器
360度LES文件浏览器功能可谓是非常强大，可以对文件或文件夹进行新建、复制、剪切、删除、移动、搜索等操作。支持多标签页，能设置成root级别的管理器, 关联文件打开,列表或图标的形式显示，拖曳文件,多标签页下文件拖曳(下面有详细的讲解)&…
XML DTD 语言学习笔记
-XML DTD 全称：Document Type Definition简介：用于定义文档的合法性。它定义了文档应该有哪些元素及其属性，还有其他一些约束性规则。 注意：DTD语言定义的文档类型是SGML家族的标记性语言。包括SGML,XML,HTML）…
Python快速入门，你想要的就在这里了！
学习Python您是否会面临以下问题？“网上充斥着大量的学习资源、书籍、视频教程和博客，但是大部分都是讲解基础知识，不够深入；也有的比较晦涩，难以理解”CSDN Python学习社群将帮助您过滤网上的垃圾教程资源的技能&…
设计模式之代理模式(Proxy)摘录
23种GOF设计模式一般分为三大类：创建型模式、结构型模式、行为模式。 创建型模式抽象了实例化过程，它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类，而一个对象创建型模式将实例化委托给…
Symfony学习笔记
Symfony学习笔记Symfony本来已经接触过了，可发现好久 不用好多东西都已经遗忘了，决定再次拾起，看能不能发现之前没有注意到的新的东西。果然在不断学习的过程中，又发现了许多自认为很细节但又很重要的地方，下面就列举如…
设计模式之模板方法模式(Template Method)摘录
23种GOF设计模式一般分为三大类：创建型模式、结构型模式、行为模式。 创建型模式抽象了实例化过程，它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类，而一个对象创建型模式将实例化委托给…
Linux练习（显示环境变量）
#include <stdio.h> #include <stdlib.h> extern char **environ; int main() {char **envenviron;while(*env){printf("%s\n",*env);env;}exit(0); } 主要是environ变量，定义如下 #include <stdlib> extern char **environ;
百度发布ERNIE 2.0，性能超BERT、XLNet
作者 | Khari Johnson 译者 | 赵雪 编辑 | 夕颜 出品 | AI科技大本营（ID: rgznai100） 中国科技巨头百度于今日提出了 ERNIE 2.0——一个中英双语的会话式人工智能模型。ERNIE 2.0 在语言理解基准上的表现超过了谷歌的 BERT 和 XLNet，在 9 个国…
php中mkdir()函数的权限问题
为什么80%的码农都做不了架构师？>>> 遇到个问题 某个定时job用root用户mkdir(./test/,0777)新建了目录，指定了权限是0777，结果获得的是0755, 而web上用www用户也在这目录创建目录和文件，结果报错了，一开始…
设计模式之策略模式(Strategy)摘录
23种GOF设计模式一般分为三大类：创建型模式、结构型模式、行为模式。 创建型模式抽象了实例化过程，它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类，而一个对象创建型模式将实例化委托给…
PreparedStatement
该 PreparedStatement接口继承Statement，并与之在两方面有所不同： PreparedStatement 实例包含已编译的 SQL 语句。这就是使语句“准备好”。包含于 PreparedStatement 对象中的 SQL 语句可具有一个或多个 IN 参数。IN参数的值在 SQL 语句创建时未被指…
百度ERNIE 2.0发布！16项中英文任务表现超越BERT和XLNet
整理 | 夕颜出品 | AI科技大本营（ID:rgznai100）导读：2019 年 3 月，百度正式发布 NLP 模型 ERNIE，其在中文任务中全面超越 BERT 一度引发业界广泛关注和探讨。今天，百度发布了 ERNIE 2.0，指出其在…
WindowsServer2012史记7-茴香豆的五种写法和四种”显示计算机”的方法
消失的"计算机"？【这周九叔工作比较忙，还有其他琐事缠身，因此SystemCenter2012SP1系列的发布稍慢，抱歉了各位。】众所周知，WindowsServer2012和Windows8一样，默认桌面上是没有"计算机"…
设计模式之状态模式(State)摘录
23种GOF设计模式一般分为三大类：创建型模式、结构型模式、行为模式。 创建型模式抽象了实例化过程，它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类，而一个对象创建型模式将实例化委托给…
CYQ学习主要摘要4
http://www.cnblogs.com/cyq1162/archive/2010/11/03/1867642.html Xml的处理 http://www.cnblogs.com/cyq1162/archive/2010/11/23/1885299.html 3.5版本 http://www.cnblogs.com/cyq1162/archive/2010/12/27/1918317.html 无线分级 http://www.cnblogs.com/cyq1162/archive/2…
知识图谱、深度学习、AutoML，推荐系统与新技术结合将碰撞出怎样的火花？
近日，来自意大利米兰理工大学 Maurizio 团队发表的一篇极具批判性的文章火了。这篇文章剑指推荐系统领域的其他数十篇论文，并通过多项试验证明这些论文中基于深度学习的推荐算法大部分都存在不同程度的数据集缺失和源码缺失的问题，导致根本无…
python-range用法
2019独角兽企业重金招聘Python工程师标准>>> 详细记录python的range()函数用法 转载于:https://my.oschina.net/lxwgmail/blog/135228
设计模式之观察者模式(Observer)摘录
23种GOF设计模式一般分为三大类：创建型模式、结构型模式、行为模式。 创建型模式抽象了实例化过程，它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类，而一个对象创建型模式将实例化委托给…
中科院、百度研究院等联合提出UGAN，生成图片难以溯源
作者 | 中国科学院、北京航空航天大学、百度研究院团队译者 | 凯隐编辑 | 夕颜出品 | AI科技大本营（ID: rgznai100）导读：生成对抗网络（GAN）是近年大热的深度学习模型，中国科学院相关团队注意到，…
搜索引擎的时效性需求满足
“全、准、快、新”是搜索引擎的四大评价指标，其中的“新”指代的就是时效性。随着互联网的发展，网民对信息获取的时效性要求越来越高。同时越来越多的网民更多的参与到创造互联网内容中去，互联网上的新信息也在迅速的膨胀。这都给搜索引擎时…
如何卸载sql2008，完全清除
1.先把SQL Server卸载，再把安装时产生的“Microsoft SQL Server”文件夹删掉,在运行注册表,把HKEY_CURRENT_USER\Software\Microsoft\Microsoft SQLServer，HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Microsoft SQL Server全部删掉，(注意要把Mic…
别再说学不会：超棒的Numpy可视化学习教程来了
作者 | Jay Alammar译者 | 苏南下来源 | 机器会学ML（ID：AI_Learning007）导读：学习 Python，尤其是基于 Python 的学习机器学习算法，最基础的 NumPy 用法必须得熟悉。网上这方面的教程不少，但大多…