这位多产的研讨者发现了随机性和较量争论之间的深刻分割，其奉献影响了密码学、复杂性等多个范畴的研讨。
今年的图灵奖，比往年来的要晚一些。北京时间 4 月10日晚，较量争论机协会ACM宣布将2023图灵奖授予普林斯顿初等研讨院数学家和顶级表面较量争论机科学家阿维·威格森（Avi Wigderson），以表彰他对较量争论表面的基础性奉献，包括塑造对较量争论中随机性作用的懂得，以及数十年来在表面较量争论机科学范畴的卓越领导力。
Wigderson为普林斯顿初等研讨院数学学院的Herbert H. Maass教授，在较量争论复杂性表面、算法和优化、随机性和密码学、并行和分布式较量争论、组合学、图论以及表面较量争论机科学与数学、科学之间的关联等范畴都是领军学者。
他从 20 世纪 90 年代开始在随机性和较量争论方面的职责揭示了数学和较量争论机科学之间的深刻分割，这些职责是当今研讨的重要基础。荣获 2002 年 Rolf Nevanlinna 奖（现称 Abacus 奖）的哈佛大学较量争论机科学家 Madhu Sudan 表示，Wigderson 在该范畴的影响不容忽视。「在较量争论机科学的任何范畴职责，如果不与 Avi 的职责真正交叉，都是非常困难的，」Sudan 表示。「在任何地方，你都会发现非常深刻的见解。」Wigderson 在以色列海法长大，是一名护士和一名电气工程师的三个儿子之一。他的父亲喜欢拼图，并对数学的基本概念非常感兴趣，他与孩子们分享了这些想法。「我就是被他的气质所感染的人，」Wigderson表示。在 20 世纪 70 年代，当他在海法大学开始上本科时，他想主修数学，但他的父母却引导他选择了较量争论机科学。「他们认为我毕业后能找到一份职责也许是个好主意，」他说。
Avi Wigderson 在 UC Berkeley 的图书馆。在学习过程中，他发现这个范畴充满了深刻的、尚未解答的数学题目。Wigderson 最早的开创性努力之一集中在一个看似矛盾的题目上：是否有可能让其他人相信一个数学陈述已经被注明，而不显示如何注明。普林斯顿大学较量争论机科学家 Ran Raz 表示：「看到注明的人对注明本身一无所知。」1985 年，Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 引入了零知识交互式注明的概念，并演示了其在一些语句中的用途。Wigderson 与 Micali 和 Oded Goldreich 后来阐述了这个想法，列出了条件，表明如果一个陈述可以被注明，它也有一个零知识注明。「这是密码学的一个关键结果，它非常核心，」Raz 说道。使用零知识注明，某人可以注明他们使用自己的密钥正确加密或签署了消息，而无需透露任何相关信息。「Avi 在密码学方面有一些极其重要的成果，这可能是其中最重要的。」但也许 Wigderson 最重要的奉献在于另一个范畴：将较量争论难度与随机性分割起来。
到 20 世纪 70 年代末，较量争论机科学家已经意识到，对于许多难题，采用随机性的算法（也称为几率算法）可以远远胜过其确定性替代方案。例如，在 1977 年的注明中，Robert Solovay 和 Volker Strassen 引入了一种随机算法，可以比当时最好的确定性算法更快地确定一个数字是否为素数。对于某些题目，几率算法可以指向确定性算法。20 世纪 80 年代初，Wigderson 与加州大学伯克利分校的 Richard Karp 合作，将随机性的概念与较量争论困难的题目分割起来，这意味着没有已知的确定性算法可以在合理的时间内处理这些题目。「我们不知道如何注明它们很困难，」 Wigderson说。然而，他和 Karp 发现了一种针对某个难题的随机算法，后来他们能够将其去随机化，从而无效地揭示了它的确定性算法。大约在同一时间，其他研讨人员展示了密码学题目中的较量争论难度假设如何能够实现一般的去随机化。随机性的不合理无效性促使他思考随机性本身的本质。他和当时的其他研讨人员一样，质疑它对于无效处理题目的必要性以及在什么条件下可以完全消除它。「最初，并不清楚这是否只是我们自己的愚蠢，我们无法消除随机性，」Wigderson 说道。「但更大的题目是随机性是否总能无效消除。」他意识到对随机性的需求与题目的较量争论难度密切相关。在 1994 年的一篇论文中，他和较量争论机科学家 Noam Nisan 阐明了这种分割。他们注明，如果存在任何自然难题，正如大多数较量争论机科学家所怀疑的那样，那么每一种无效的随机算法都可以被无效的确定性算法所取代。「你总是可以消除随机性，」Wigderson 说道。重要的是，他们发现确定性算法可能使用「伪随机」序列——看似随机但实际上并非随机的数据串。他们还展示了如何使用任何难题来构建伪随机生成器。将伪随机位（而不是随机位）输入几率算法将为同一题目产生无效的确定性算法。Sudan 表示，这篇论文帮助较量争论机科学家认识到随机性的程度，有助于揭示难题的复杂性以及如何处理它们。「这不仅仅是随机性，还有对随机性的看法，」他说。「这就是关键。」随机性似乎无处不在，但事实上却很难找到。「人们告诉你，圆周率的数字看起来是随机的，或者素数的数字序列看起来是随机的，」Sudan 介绍道。「它们是完全确定的，但对我们来说它们似乎是随机的。」对随机性的感知是当今较量争论机科学的核心。这就是 Avi 大力提倡的事情。随机性已成为复杂性表面中的强大资源，但它却难以捉摸。Wigderson 指出，抛硬币和掷骰子并不是真正随机的：如果你有足够的关于物理系统的信息，那么结果是完全可以预测的。完美的随机性是难以捉摸且难以验证的。对于 Avi Wigderson 来说，可较量争论的例子无处不在——不仅在智能手机、笔记本电脑和加密算法中，而且在生物和物理系统中。近几十年来，较量争论表面的研讨成果让人们对一系列意想不到的题目有了深入的了解，从鸟类群体、选举结果到体内的生化反应。「基本上，任何自然过程都是一种进化，你可以将其视为较量争论，因此你可以这样研讨它。几乎所有事情都需要较量争论，」Wigderson 说道。此前，Wigderson 还与布达佩斯罗兰大学的数学家László Lovász共享了2021年的阿贝尔奖，该奖被誉为是数学界的诺贝尔奖。由此，他也成为了唯一一个同时摘得数学范畴阿贝尔奖和较量争论机科学范畴图灵奖的学者。参见机器之心报道：2021 数学界 “诺奖” 阿贝尔奖揭晓，两位密码学大佬获得殊荣
今日，在接受普林斯顿初等研讨院主任及Leon Levy教授David Nirenberg采访时，现年67岁的Wigderson表示自己既是数学家也是较量争论机科学家。
2012 年图灵奖得主、西蒙斯较量争论表面研讨所所长、前普林斯顿初等研讨院的客座教授Shafi Goldwasser表示， Wigderson对从并行算法到密码学、复杂性表面等众多范畴的较量争论表面都做出了基础性奉献。几十年来，他在去随机化和伪随机性方面做出了大量奉献，使人们可以更深入地了解随机性在较量争论中的深层作用。图灵奖是ACM于1966年设立的奖项，专门奖励对较量争论机事业作出重要奉献的个人，有着「较量争论机界诺贝尔奖」之称，奖金为100万美元，由谷歌赞助。图灵奖的名称取自英国数学家艾伦·图灵（Alan M. Turing），他奠定了较量争论机的数学基础，也阐述了其局限性。
什么是表面较量争论机科学？
表面较量争论机科学与该范畴的数学基础相关。它提出的题目包括：「这个题目是否可以通过较量争论处理？」或「如果这个题目可以通过较量争论处理，需要多少时间和其他资源？」表面较量争论机科学还探索高效算法的设计。与我们生活息息相关的每一项较量争论技术都是通过算法实现的，了解强大高效算法的原理，不仅能加深对较量争论机科学的懂得，还能加深对自然规律的懂得。这是一个提出「智力挑战」的范畴，通常并不直接涉及改进较量争论的实际应用，但相关研讨突破几乎推动了该范畴各个范畴的进步——从密码学和较量争论生物学到网络设计、机器学习和量子较量争论。
为什么随机性很重要？
从根本上来说，较量争论机是确定性系统。应用于任何给定输入的算法指令集唯一地决定了其较量争论，尤其是其输出。换句话说，确定性算法遵循可预测的模式。相比之下，随机性缺乏明确的模式，或者说事件或结果的可预测性。由于我们生活的世界似乎充满了随机事件（天气系统、生物和量子现象等），较量争论机科学家通过允许算法在较量争论过程中做出随机选择来丰富算法，以期提高算法的效率。而且事实上，许多尚无无效确定性算法的题目已经可以通过几率算法得到无效处理，尽管存在一些小几率误差（可以无效减少）。但随机性是必不可少的还是可以消除的？几率算法成功所需的随机性质量是多少？这些以及许多其他基本题目是懂得较量争论中的随机性和伪随机性的核心。对较量争论中随机性动态的更好懂得，可以使我们开发出更好的算法，并加深我们对较量争论本身本质的懂得。
Wigderson的奉献
四十年来，作为表面较量争论机科学研讨范畴的领军人物，Wigderson在懂得随机性和伪随机性在较量争论中的作用方面做出了奠基性的奉献。较量争论机科学家发现了随机性与较量争论难度（即确定没有高效算法的自然题目）之间的显著分割。作为较量争论复杂性表面家，Wigderson不一定关心这些题目的答案。他常常只是想知道这些题目是否可以处理，以及如何判断。Wigderson与同事合作，撰写了一系列极具影响力的关于用随机性换取难度的著作。他们注明，在标准的、被广泛相信的较量争论假设下，每一种几率多项式时间算法都可以无效地去随机化（即完全确定）。换句话说，随机性并不是高效较量争论的必要条件。这一系列著作彻底改变了人们对随机性在较量争论中的作用的懂得，也改变了人们对随机性的思考方式。三篇影响深远的论文包括：《Hardness vs. Randomness》（与Noam Nisan合著）：这篇论文还介绍了一种新型伪随机发生器，并注明了在比以前已知的假设更弱的条件下，可以对随机算法进行高效的确定性模拟。
论文链接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf
《BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs》（与László Babai、Lance Fortnow、Noam Nisan合著）：本文利用 Hardness Amplification 注明，在较弱的假设条件下，有界错误几率多项式时间（BPP）可以在亚指数时间内模拟无限多的输入长度。
论文链接：https://link.springer.com/article/10.1007/BF01275486
《P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma》（与Russell Impagliazzo合著）：本文介绍了一种更强的伪随机发生器，它在难度与随机性之间实现了基本最优的权衡。
论文链接：https://dl.acm.org/doi/pdf/10.1145/258533.258590Wigderson这三篇论文的影响远远超出了随机性和去随机化范畴。这些论文中的观点随后被应用于表面较量争论机科学的许多范畴，并激发了该范畴多位领军人物发表具有影响力的论文。
目前，Wigderson与Omer Reingold、Salil Vadhan、Michael Capalbo合作，仍然在较量争论随机性的广泛范畴开展职责，在一篇论文中首次提出了扩展图的高效组合构造（https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf）。扩展图是一种稀疏图，具有很强的连通性，在数学和表面较量争论机科学范畴都有许多重要应用。
除了在随机性方面的研讨之外，Wigderson还是表面较量争论机科学其他几个范畴的知识领袖，包括多验证器交互式注明、密码学和电路复杂性。
受人尊敬的导师
除了突破性的技术奉献外，Wigderson还被认为是一位受人尊敬的导师和同事，为无数年轻研讨人员提供了建议。他渊博的知识和无与伦比的专业性，加上他的友善、热情和慷慨，吸引了许多最优秀的年轻人从事表面较量争论机科学事业。「需要指出的是，Avi Wigderson 还获得了阿贝尔奖，该奖被认为是数学范畴终身成就的最重要荣誉，」ACM 主席雅尼斯·约安尼迪斯 (Yannis Ioannidis) 解释道。「被选为 ACM A.M.图灵奖得主是一个合适的后续奖励，因为数学是较量争论机科学的基础，而 Wigderson 的职责将广泛的数学子范畴与表面较量争论机科学分割起来。Wigderson是表面较量争论机科学范畴杰出的一支力量，也是一门令人兴奋的学科，吸引了一些最有前途的年轻研讨人员来处理最困难的挑战。今年的图灵奖表彰了 Wigderson 在随机性方面的具体职责，以及他对整个表面较量争论机科学范畴产生的间接但实质性的影响。」谷歌高级副总裁 Jeff Dean 表示：「Avi Wigderson 在随机性和其他主题方面的职责为过去三十年表面较量争论机科学的发展设定了研讨议程。」「从较量争论机科学的早期开始，研讨人员就认识到，结合随机性是一种设计快速、广泛应用算法的好方法。更好地懂得随机性为我们的范畴带来重要的收益，而 Wigderson 在这一范畴开辟了新的视野。谷歌也向 Wigderson 作为导师的角色致敬。他的同事们称赞他提出了伟大的想法和研讨方向，然后激励了新一代年轻研讨人员致力于这些研讨。我们祝贺 Avi Wigderson 荣获较量争论机范畴的最高荣誉ACM A.M.图灵奖。」
大奖拿遍的Wigderson
自 1999 年以来，Avi Wigderson一直担任新泽西州普林斯顿初等研讨院数学学院Herbert H. Maass教授。此前，他曾担任耶路撒冷希伯来大学教授，并在普林斯顿大学、加州大学伯克利分校、IBM 等机构担任访问职位。Wigderson 毕业于以色列理工学院，并获得普林斯顿大学文学硕士、工程科学硕士和较量争论机科学博士学位。Wigderson获得的荣誉包括阿贝尔奖、国际数学联盟算盘奖（以前称为内万林纳奖）、高德纳奖、Edsger W. Dijkstra 分布式较量争论奖和哥德尔奖。他是 ACM Fellow、美国国家科学院和美国艺术与科学院院士。
参考链接：https://amturing.acm.org/award_winners/wigderson_3844537.cfmhttps://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/https://www.ias.edu/news/avi-wigderson-2023-acm-am-turing-award