美华社区

阿维·维格德森（Avi Wigderson）获得计算机界诺奖级的2023图灵奖，曾获数学界的诺奖级的终身成就奖2021阿贝尔奖

博士Ph.D. ，普林斯顿大学Princeton University （1983）
博士论文： Studies in Computational Complexity (1983)
导师： 理查德·利普顿（Richard Lipton）

现职： 普林斯顿高等研究院数学学院Herbert H. Maass教授
Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton

早期教育：
中学：海法希伯来瑞利学校Hebrew Reali School in Haifa
本科：海法以色列理工学院The Technion in Haifa

赞，很谦虚的一个人，

heartstorm 写了： ↑周五 4月 12, 2024 1:40 pm 赞，很谦虚的一个人，

嗯嗯。

量子位 2024-04-10


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

维格森于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年时间，建议同学们要选择自己喜欢的研究领域和话题，并享受在失败中不断学习的过程，这样才能在科研道路上走得长远。

图灵人工智能 ｜2024-04-12

Wigderson的贡献

四十年来，Wigderson作为理论计算机科学研究领域的领军人物，对理解随机性和伪随机性在计算中的作用做出了奠基性贡献。

计算机科学家发现随机性与计算难度（即识别没有高效算法的自然问题）之间有显著联系。Wigderson与同事合作撰写了一系列极具影响力的关于用难度换取随机性的著作。他们证明，在标准、广泛认可的计算假设下，每一种概率多项式时间算法都可以有效去随机化（即完全确定）。换句话说，随机性并不是高效计算的必要条件。该系列著作彻底改变了我们对随机性在计算中的作用的理解，以及我们思考随机性的方式。该系列有影响力的论文包括以下三篇：

“难度与机性”（与 Noam Nisan 合著）

除其他发现外，该论文还介绍了一种新型伪随机发生器，并证明了在比以前所知更弱的假设下，可以对随机算法进行高效确定性模拟。

“除非指数时间有可发布的证明，否则BPP有亚指数时间模拟”（与 László Babai、Lance Fortnow 和 Noam Nisan 合著）

该论文利用“难度放大”证明在弱假设下可以在亚指数时间内模拟无限多输入长度的有限错误概率多项式时间（BPP）。

“P=BPP（如果E需要指数电路）：将XOR Lemma去随机化”（与Russell Impagliazzo合著）

该论文介绍一种更强的伪随机发生器，其在本质上实现了难度与随机性之间的最优权衡。

重要的是，Wigderson的这三篇论文的影响远远超出了随机性和去随机化领域。这些论文中的观点随后被应用于理论计算机科学的许多领域，并引领该领域多位领军人物发表有影响力的论文。

Wigderson仍然在计算随机性的广泛领域开展工作，在他与Omer Reingold、Salil Vadhan和Michael Capalbo合著的论文中首次提出了扩展图的高效组合构造，该扩展图是具有强连接特性的稀疏图。它们在数学和理论计算机科学领域都有许多重要应用。

除随机性方面的工作以外，Wigderson还是理论计算机科学的其他多个领域的知识领袖，包括多验证人交互式证明、密码学和电路复杂性。

指 导

除开创性技术贡献以外，Wigderson还是一位广受尊敬的导师和同事，指导过无数年轻研究人员。他广博的知识和出众的技术能力，再加上他的友善、热情和慷慨，吸引了许多最优秀的年轻人投身于理论计算机科学领域。

“必须指出的是，Avi Wigderson还获得了阿贝尔奖，该奖项被认为是数学领域最重要的终身成就荣誉，”ACM总裁Yannis Ioannidis解释说。“获得ACM A.M.图灵奖是水到渠成的——因为数学是计算机科学的基础，而Wigderson的工作将广泛的数学子领域与理论计算机科学联系在一起。Wigderson代表理论计算机科学领域的强大的知识力量，这门令人兴奋的学科吸引了一些最有前途的年轻研究人员来攻克最艰巨的挑战。今年的图灵奖表彰Wigderson在随机性方面的具体工作，以及他对整个理论计算机科学领域产生的间接但实质的影响。

“在过去三十年里，Avi Wigderson在随机性和其他课题方面的工作决定了理论计算机科学的研究方向，”谷歌高级副总裁 Jeff Dean 解释说。“从计算机科学诞生之初，研究人员就已认识到，结合随机性是为广泛应用设计更快算法的一种方法。努力更好地理解随机性将继续为我们的领域带来重要益处。谷歌还向Wigderson的导师角色致敬。他的同事们认为他提出了伟大的想法和研究方向，并激励着新一代聪明的年轻研究人员为之努力。我们祝贺Avi Wigderson获得ACM A.M.图灵奖这一计算机领域的最高荣誉。”

Reference

难度与随机性

除非指数时间有可发布的证明，否则BPP有亚指数时间模拟