温哥华Lipont Place力邦艺术港:活动场地租赁,拍摄场地租赁!

计算机圈30年猜想 华人数学家解决

QR Code
请用微信 扫一扫 扫描上面的二维码,然后点击页面右上角的 ... 图标,然后点击 发送给朋友分享到朋友圈,谢谢!
  1992年,布尔函数敏感度猜想被提出。这成为了理论计算机科学近三十年来最重要的开放性问题之一。近日,来自Emory大学计算机与数学科学系的华人教授黄皓,用两页纸轻松证明了困扰理论计算机领域数十年的问题。

  组成计算机的电路实际上是“与”“或”“非”逻辑电路的组合,多年来,计算机科学家已经开发出许多方法来测量给定布尔函数的复杂性。

  科学家们发现,关于布尔函数的度量措施都适用于一个统一的框架,只有一个复杂性指标似乎不合适:“灵敏度”。1992年,耶路撒冷希伯来大学的Noam Nisan和现在罗格斯大学的Mario Szegedy推测,“灵敏度”的确适合这一框架,但没人能证明这一点。“我想说,这可能是布尔函数研究中一个悬而未决的问题。”Servedio说。


  现在,Emory大学的数学家黄皓用一个巧妙但简单的两页论证,证明了灵敏度猜想,这个论点关于立方体上的点的组合。

  法国国家科学研究中心的Claire Mathieu在接受Skype采访时曾评价它为:“这只是一颗美丽的珍珠。”

  黄皓是谁?这位华人科学家是怎么解开30年来一直困扰计算机科学家的问题呢?

  华人数学家——黄皓

  黄皓出生于汕头,这座海滨城市同时也是另一位着名数学家丘成桐的出生地。

  十四岁的时候,黄皓就离开家乡奔赴广州华南师范大学附属中学就读。凭借优异的成绩,2003年黄皓被保送至北京大学攻读数学专业。在北大就读时,黄皓就在北京大学举办的首届“江泽涵”杯数学建模与计算机应用竞赛中获得三等奖,并出现在北大数学百年学生名录上。

  2007年北大本科毕业后,黄皓在美国加州大学洛杉矶分校读博,师从国际着名数学家Benny Sudakov教授,并于2012年获得博士学位。


  曾在2012-2014年受邀访问美国普林斯顿高等研究院,现担任美国艾默里大学数学系助理教授。主要研究领域包括极值组合、图论及计算机理论。

  

  一次偶然与猜想的邂逅


  2012年末,在受访美国普林斯顿高等研究院期间,黄先生在与数学家Michael Saks共进午餐时听说了敏感性猜想,黄先生是博士后研究员。他立刻被这个猜想的简洁和优雅所吸引。“从那一刻开始,我开始沉迷于思考它。”他说。

  黄将敏感性猜想添加到他感兴趣问题的“秘密列表”中,每当他学习新的数学工具时,他都会考虑它是否有帮助。“每次我发表新论文后,我都会回到这个问题,”他说。“当然,我会在一段时间后放弃,并解决一些更现实的问题。”

  正如其他研究团体一样,黄知道,如果数学家可以证明一个关于不同维度立方体上的点集合比较容易陈述的猜想,那么灵敏度猜想就可以得到解决。从n个0和1的字符串到n维立方体上的点有一种自然的映射关系。

  在2013年,黄开始认为理解这个问题的最佳途径可能是通过标准网络来表示网络,该矩阵跟踪哪些点连接,然后检查一组称为矩阵特征值的数字。五年来,他一直在重新审视这个想法,没有成功。

  “但至少考虑它可以帮助我很快入睡。”他在Aaronson的博客文章中评论道。

  然后在2018年,黄发现了使用一个有200年历史的称为Cauchy交错定理的数学,它将矩阵的特征值与子矩阵的特征值联系起来,使其成为研究立方体与立方体之间关系的完美工具。黄决定要求国家科学基金会拨款,以进一步探讨这一想法。
您的点赞是对我们的鼓励     无评论不新闻,发表一下您的意见吧
上一页123下一页
注:
  • 新闻来源于其它媒体,内容不代表本站立场!
  • 在此页阅读全文

    猜您喜欢

    您可能也喜欢

    当前评论

    当前评论目前还没有任何评论,欢迎您发表您的看法。
    发表评论
    您的评论 *:
    安全校验码 *:
    请在此处输入图片中的数字
    The Captcha image
      (请在此处输入图片中的数字)

    Copyright © 加西网, all rights are reserved.

    加西网为北美中文网传媒集团旗下网站