用户名:  密码:   
网站首页即时通讯活动公告最新消息科技前沿学人动向两岸三地人在海外历届活动关于我们联系我们申请加入
栏目导航 — 美国华裔教授专家网最新消息社区报道
关键字  范围   
 
华人数学家黄皓只用了两页就解决了令人困惑三十年的计算机科学猜想
华人数学家黄皓只用了两页就解决了令人困惑三十年的计算机科学猜想
2019/7/26 0:53:20 | 浏览:3274 | 评论:0

布尔函数的敏感度猜想:n维超立方体的诱导子图,如果包含超过半数顶点,那么必然有一个顶点的度至少是n的平方根。以前几个院士合作的一篇文章中证明的下界是log(n)。

 

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

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

                                   


华人数学家黄皓只用了两页就解决了令人困惑三十年的计算机科学猜想             

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/

Decades-Old Computer Science Conjecture Solved in Two Pages
 
The “sensitivity” conjecture stumped many top computer scientists, yet the new proof is so simple that one researcher summed it up in a single tweet.

华人数学家黄皓只用了两页就解决了令人困惑三十年的计算机科学猜想

A paper posted online this month has settled a nearly 30-year-old conjecture about the structure of the fundamental building blocks of computer circuits. This “sensitivity” conjecture has stumped many of the most prominent computer scientists over the years, yet the new proof is so simple that one researcher summed it up in a single tweet.

“This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,” wrote Scott Aaronson of the University of Texas, Austin, in a blog post. “The list of people who tried to solve it and failed is like a who’s who of discrete math and theoretical computer science,” he added in an email.

The conjecture concerns Boolean functions, rules for transforming a string of input bits(0s and 1s)into a single output bit. One such rule is to output a 1 provided any of the input bits is 1, and a 0 otherwise; another rule is to output a 0 if the string has an even number of 1s, and a 1 otherwise. Every computer circuit is some combination of Boolean functions, making them “the bricks and mortar of whatever you’re doing in computer science,” said Rocco Servedio of Columbia University.

I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this.

Scott Aaronson

Over the years, computer scientists have developed many ways to measure the complexity of a given Boolean function. Each measure captures a different aspect of how the information in the input string determines the output bit. For instance, the “sensitivity” of a Boolean function tracks, roughly speaking, the likelihood that flipping a single input bit will alter the output bit. And “query complexity” calculates how many input bits you have to ask about before you can be sure of the output.

Each measure provides a unique window into the structure of the Boolean function. Yet computer scientists have found that nearly all these measures fit into a unified framework, so that the value of any one of them is a rough gauge for the value of the others. Only one complexity measure didn’t seem to fit in:sensitivity.

In 1992, Noam Nisan of the Hebrew University of Jerusalem and Mario Szegedy, now of Rutgers University, conjectured that sensitivity does indeed fit into this framework. But no one could prove it. “This, I would say, probably was the outstanding open question in the study of Boolean functions,” Servedio said.

“People wrote long, complicated papers trying to make the tiniest progress,” said Ryan O’Donnell of Carnegie Mellon University.

Now Hao Huang, a mathematician at Emory University, has proved the sensitivity conjecture with an ingenious but elementary two-page argument about the combinatorics of points on cubes. “It is just beautiful, like a precious pearl,” wrote Claire Mathieu, of the French National Center for Scientific Research, during a Skype interview.

Aaronson and O’Donnell both called Huang’s paper the “book” proof of the sensitivity conjecture, referring to Paul Erdős’ notion of a celestial book in which God writes the perfect proof of every theorem. “I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this,” Aaronson wrote.

A Sensitive Matter
Imagine, Mathieu said, that you are filling out a series of yes/no questions on a bank loan application. When you’re done, the banker will score your results and tell you whether you qualify for a loan. This process is a Boolean function:Your answers are the input bits, and the banker’s decision is the output bit.

If your application gets denied, you might wonder whether you could have changed the outcome by lying on a single question — perhaps, by claiming that you earn more than $50,000 when you really don’t. If that lie would have flipped the outcome, computer scientists say that the Boolean function is “sensitive” to the value of that particular bit. If, say, there are seven different lies you could have told that would have each separately flipped the outcome, then for your loan profile, the sensitivity of the Boolean function is seven.

Computer scientists define the overall sensitivity of the Boolean function as the biggest sensitivity value when looking at all the different possible loan profiles. In some sense, this measure calculates how many of the questions are truly important in the most borderline cases — the applications that could most easily have swung the other way if they’d been ever so slightly different.

华人数学家黄皓只用了两页就解决了令人困惑三十年的计算机科学猜想

Sensitivity is usually one of the easiest complexity measures to compute, but it’s far from the only illuminating measure. For instance, instead of handing you a paper application, the banker could have interviewed you, starting with a single question and then using your answer to determine what question to ask next. The largest number of questions the banker would ever need to ask before reaching a decision is the Boolean function’s query complexity.

This measure arises in a host of settings — for instance, a doctor might want to send a patient for as few tests as possible before reaching a diagnosis, or a machine learning expert might want an algorithm to examine as few features of an object as possible before classifying it. “In a lot of situations — diagnostic situations or learning situations — you’re really happy if the underlying rule … has low query complexity,” O’Donnell said.

Other measures involve looking for the simplest way to write the Boolean function as a mathematical expression, or calculating how many answers the banker would have to show a boss to prove they had made the right loan decision. There’s even a quantum physics version of query complexity in which the banker can ask a “superposition” of several questions at the same time. Figuring out how this measure relates to other complexity measures has helped researchers understand the limitations of quantum algorithms.

With the single exception of sensitivity, computer scientists proved that all these measures are closely linked. Specifically, they have a polynomial relationship to each other — for example, one measure might be roughly the square or cube or square root of another. Only sensitivity stubbornly refused to fit into this neat characterization. Many researchers suspected that it did indeed belong, but they couldn’t prove that there were no strange Boolean functions out there whose sensitivity had an exponential rather than polynomial relationship to the other measures, which in this setting would mean that the sensitivity measure is vastly smaller than the other measures.

“This question was a thorn in people’s sides for 30 years,” Aaronson said.

Cornering the Solution
Huang heard about the sensitivity conjecture in late 2012, over lunch with the mathematician Michael Saks at the Institute for Advanced Study, where Huang was a postdoctoral fellow. He was immediately taken with the conjecture’s simplicity and elegance. “Starting from that moment, I became really obsessed with thinking about it,” he said.

Huang added the sensitivity conjecture to a “secret list” of problems he was interested in, and whenever he learned about a new mathematical tool, he considered whether it might help. “Every time after I’d publish a new paper, I would always go back to this problem,” he said. “Of course, I would give up after a certain amount of time and work on some more realistic problem.”

相关栏目:『社区报道
藏在美国国家档案馆的绝密照片 2024-03-23 [212]
呵呵,果然放开面上申请限制不是啥好事儿 2024-03-22 [136]
蒋碧薇:与徐悲鸿私奔的大家闺秀,因“情”跌宕孤独终老 2024-03-22 [134]
15位心理学家荣获2024年APS终身成就奖 2024-03-21 [114]
Can we still trust the polls? 2024-03-19 [185]
Meet Hugo Miller, the first male dancer on the Trojan Dance Force 2024-03-19 [175]
USC Latino Alumni Association sets ambitious goals after raising more than $1 million in a single night 2024-03-19 [90]
AI女友热潮席卷而来,下载量竟是AI男友七倍 2024-03-19 [162]
房产经纪业大地震:美国已取消佣金或影响加拿大 2024-03-19 [242]
她用12年,从“凑数员工”,逆袭成百事首位女CEO 2024-03-15 [203]
相关栏目更多文章
最新图文:
慕波:爬取7万条帖子  看看人们都是怎么吐槽相亲的 :陈文玲: 必须推动中美关系回到正确轨道 Colleen Flaherty 翻译 刘勤:MIT教授发文《美国经济评论》 :生命科学受益于明星科学家们的死亡 :北京和上海金融人的最新鄙视链 :日本政府《氢能利用进度表》 :美国《2016-2045年新兴科技趋势报告》 :天津工业大学“经纬英才”引进计划 :浙江财经大学国际青年学者论坛的邀请函 (10/31-11/1)
更多最新图文
更多《即时通讯》>>
 
打印本文章
 
您的名字:
电子邮件:
留言内容:
注意: 留言内容不要超过4000字,否则会被截断。
未 审 核:  是
  
关于我们联系我们申请加入后台管理设为主页加入收藏
美国华裔教授专家网版权所有,谢绝拷贝。如欲选登或发表,请与美国华裔教授专家网联系。
Copyright © 2024 ScholarsUpdate.com. All Rights Reserved.