今天，“计算机界最高荣誉”图灵奖揭晓：


复杂性理论先驱、普林斯顿高等研究院教授艾维·维格森（Avi Wigderson）摘得。



美国计算机协会（ACM）表示，表彰他对计算理论的基础性贡献，包括重塑人类对计算中随机性作用的理解，以及数十年来在理论计算机科学领域的领导地位。


加上2021年获得的阿贝尔奖，维格森教授现在一举成为首个同时拿下数学和计算机最高奖的科学家。


（阿贝尔奖也被誉为“数学界诺贝尔奖”。）


此外，他还是2017年阿里达摩院刚成立时首批“十大祖师”之一。


业内人士纷纷赶来表示祝贺，a16z的研发主管表示：除了已有的学术成果外，也是因为他几十年来孜孜不倦的领导力，才带来理论计算机科学界的长青与活力。


比如，没有他，可能就不会有西蒙斯计算理论研究所。



值得一提的是，他还在5个月前来到清华叉院做客，对当下大语言模型的发展表达了自己的看法。


复杂性理论先驱荣获图灵奖


作为一名数学家和计算机科学家，维格森最重要的贡献就是增强了人类对计算中随机性和伪随机性作用的理解。


具体什么意思？


20世纪70年代末，计算机科学家们已经发现：


随机性和计算难度之间存在显著联系。


（这里的计算难度之高指的是那些没有有效算法，即无法在合理的时间内解决的自然问题，它们计算起来比较困难。）


通俗一点解释就是：


对于许多难题，采用随机性的算法（也称为概率算法）可以远远胜过其确定性方案。


例如，在一个被称为“1977证明”的实现中，两位科学家就引入了一种随机算法，可以比当时最好的确定性算法更快地确定一个数字是否为素数。


而在20世纪80年代初，维格森与UC伯克利的科学家Richard Karp合作，将随机性的概念与那些被认为计算难度高的问题联系起来，也就是没有已知的确定性算法可以在合理的时间内解决这些问题的问题。


尽管不知道如何证明它们很难，维格森和Richard Karp还是发现了一种针对某个难题的随机算法，然后发现：能够将其去随机化，从而有效地揭示了它的确定性算法。


大约在同一时间，其他研究人员也发现密码学问题中的计算难度假设能够实现一般的去随机化。


这促使维格森思考随机性本身的特质。


他和其他人一样，开始质疑随机性在高效问题解决中的必要性以及在什么条件下它可以完全被消除。


终于，1994年，他和另一位计算机科学家Noam Nisan阐明了两者之间的联系。


他们证明，如果存在任何自然难题，那么每一种有效的随机算法都可以被有效的确定性算法所取代。


即我们总是可以消除随机性。


更重要的是，他们还发现确定性算法可能使用“伪随机”序列——也就是看似随机但实际上并非随机的数据串。


换句话总结就是：随机性对于高效计算来说并不是必需的。


即使在没有随机性的情况下，我们仍然可以使用有效的算法来解决问题。


这一系列研究彻底改变了计算机科学家对随机性的看法，并适用于理论计算机科学的许多领域。


今天，ACM就将图灵奖这一重要荣誉颁给了维格森，主要嘉奖的就是他在如上领域的贡献。



在普林斯顿高等研究院的采访中，维格森解释自己既是一位数学家也是一位计算机理论科学家，研究的是计算领域的数学基础。


我的研究领域是数学的一个子域，但同时，我所研究的主要概念是计算。


对于理论计算机科学，他则认为这个学科拥有一个人对学术研究所能期望的所有优点，包含了一系列令人惊叹的深刻且具有重要智力意义的基本问题，而这些问题对人类、科学、生活和技术都至关重要。


（看得出老爷子满满的热爱之情了。）


而对于本次大奖，维格森则表示：


自己很高兴看到ACM再次认可计算基础理论，它确实对计算科学的实践和技术发展作出了巨大贡献。



大学被劝学计算机“好找工作”


维格森于1956年在以色列出生，是一位护士和一名电气工程师的儿子。他的父亲喜欢拼图，并对数学的基本概念非常感兴趣，然后又经常跟孩子们分享他的想法。


维格森这样描述父亲对他的潜移默化的影响：就是他让我感染了这种病毒。


不过等他要在当地海法大学上学时，本想主修数学的他，却被他的父母劝导说：


选择计算机吧，计算机好找工作！


结果他发现这个领域有很多数学问题没有解决，于是开始吭哧吭哧解决了起来。


维格森毕业于以色列理工学院和美国普林斯顿大学，1983 年凭借论文《组合复杂性的研究》获得博士学位。


他早期的一项开创性工作，就是证明了一个看似矛盾的问题：


能不能在不展示证明过程的情况下，让别人相信一个数学论断已经被证明了。


是不是想起隐私计算领域姚期智提出的百万富翁问题那味了。


那个问题就是两个百万富翁，他们想证明谁更富有，但两个人都不透露他们拥有多少财富。


而原本的这个问题其实是叫做零知识证明，这个概念最早在1985年由三位科学家引入。随后由维格森以及他的合作伙伴Micali和Oded Goldreich进一步阐述了这一想法，并发现了一个意想不到的结果：如果真正安全加密是可能的，那么 NP 中每个问题的解也都可以用零知识证明来证明。


换言之，零知识证明可以用于秘密地证明任何有关秘密数据的公开结果。


数十年来，他始终活跃在学术岗位上，并且获得诸多赞誉和奖项。1994年，他因在计算复杂性理论方面的工作获得1994年的内万林纳


博士毕业后，他在加州大学伯克利分校担任客座助理教授，在IBM担任访问科学家，并在伯克利的数学科学研究所担任研究员。1986年加入希伯来大学担任教员。


1994年，他与Omer Reingold和Salil Vadhan一起因在图的 zig-zag 乘积方面的工作而获得了 2009 年哥德尔奖。


1999年，他加入普林斯顿高等研究院并工作至今。2013年当选美国国家科学院院士。


2018年，他因对计算机科学和数学理论的贡献当选ACM Fellow。


第二年，又因为“在随机计算、密码学、电路复杂性、证明复杂性、并行计算以及我们对基本图特性的理解等领域对计算机科学基础作出的根本性和持久性贡献”，他荣获高德纳奖。


2021年，维格森与László Lovász共同获得阿贝尔奖。


也正因为这样根本性且持久性的贡献，网友们得知他才获图灵奖时感到意外而又惊喜，还以为他早就得了。



也有人开始看他曾经写过的书籍了。


或许有眼熟的朋友吗？



谈大语言模型：最重要还是看它不能做什么


而他与姚期智以及中国的缘分还在延续。


5个月前，他还曾亲自来到清华叉院做客，带来题为“模仿游戏（Imitation Games）”的特邀报告。


由姚期智院士亲自主持讲座，并与他展开对话。


据报道，维格森从图灵测试出发，叙述了“模仿学习”理论的沿革及其在密码学、随机性、离散数学、数论等领域的现代应用。


他基于凯撒密码、恩尼格玛密码机、选举等案例，引导思考安全性的定义、随机性的应用、隐私和效用的平衡等问题。


对于理论计算机研究将如何应对人工智能发展这一问题，维格森表示：


尽管包括大语言模型在内的人工智能有很多惊人表现，但最重要的问题是还有什么是AI不能做的。


对于现在正置身于科研的同学们，维格森也给出了自己的建议。


他表示，自己曾为解决一个开放性问题用了40年时间，建议同学们要选择自己喜欢的研究领域和话题，并享受在失败中不断学习的过程，这样才能在科研道路上走得长远。


参考链接：

[1]https://www.acm.org/media-center/2024/april/turing-award-2023

[2]https://www.ias.edu/news/avi-wigderson-2023-acm-am-turing-award

[3]https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/

[4]https://www.youtube.com/watch?v=TK_vD-VnsFw

[5]https://x.com/Tim_Roughgarden/status/1778032735849967818[6]https://x.com/letonyo/status/1777987622301769771


本文来自微信公众号：量子位（ID：QbitAI），作者：白交、丰色