2023图灵奖得主揭晓！史上首位计算机和数学最高奖“双料王”诞生

重磅消息！北京时间4月10日下午5点整，ACM宣布把2023年图灵奖颁给Avi Wigderson，以表彰Wigderson对计算理论和随机性做出的奠基性贡献。

ACM图灵奖通常被称为“计算机领域的诺贝尔奖”，奖金为100万美元，通常颁发给计算机科学各领域的研究领袖。

计算理论和随机性的领袖

Wigderson是普林斯顿高等研究院数学学院的教授，他是计算复杂性理论、算法和优化、随机性和密码学、并行和分布式计算、组合学和图论以及理论计算机科学与数学等科学之间的联系等领域的领军人物。^[1]

Wigderson教授，2013年当选美国国家科学院院士，2018年因对“理论计算机科学和数学的贡献”被授予ACM会士。2021年，Wigderson获得阿贝尔奖，“以表彰他们对理论计算机科学和离散数学的基础性贡献，以及他们将其塑造为现代数学的中心领域方面的领导作用”^[2]

这次Wigderson获得图灵奖，也成为了第一个同时获得过图灵奖和阿贝尔奖的人。

什么是计算理论

计算理论涉及计算机科学的数学基础。它提出的问题包括“这个问题是否可以通过计算解决”和“如果这个问题可以通过计算解决，需要多少时间和其他资源？”

计算理论还探索高效算法的设计，虽然并不直接涉及改进计算的实际应用，但其研究成果是计算机科学各领域的基础，比如密码学、计算生物学、网络设计、机器学习和量子计算等。

什么是计算的随机性

计算的随机性研究是计算理论的一个子集，从根本上来说，计算机是确定性系统，意味着给定特定的输入，算法的指令集将准确预测计算的输出。

然而，现实世界充斥着难以预测的随机事件，如天气变化和量子现象。为了提升算法效率，计算机科学家引入了能在计算过程中进行随机选择的概率算法，成功解决了一些难以找到有效确定性解决方案的问题，尽管这些算法可能包含微小的误差概率。

这引出了是否能完全去除随机性、所需随机性的质量，以及如何理解和利用计算中的随机性与伪随机性等基本问题。深入理解这些动态将有助于我们开发更好的算法，并深化对计算本质的认识。

Wigderson的卓越贡献

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

上世纪40年代，乌拉姆和冯·诺依曼共同发明的蒙特卡罗方法，开启了随机算法的先河。

在上世纪70年代末，计算机科学家们已经发现：随机性和计算难度之间存在显著联系，对于许多难题，采用随机性的算法（也称为概率算法）可以远远胜过其确定性方案，比如当时的拉斯维加斯算法。

在80年代，BPP复杂性类的建立，标志着对随机算法计算复杂性系统性研究的开始，BPP类描述了那些可以在多项式时间内解决且具有误差概率的算法。Wigderson在该领域的三项研究深远地影响了计算机科学的各个学科：

Hardness vs. Randomness

BPP has subexponential time simulations unlessEXPTIME has publishable

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma

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

图灵奖背后的故事

Wigderson教授，1956年出生于以色列海法。Wigderson的父亲是一名电气工程师。他的父亲喜欢拼图，并对数学的基本概念非常感兴趣，然后又经常跟孩子们分享他的想法。

Wigderson在采访中这样描述父亲对他的影响：就是他让我感染了数学这种“病毒”。

本来大学想主修数学专业的他，却被父母劝导学计算机，理由是:

计算机科学是一个年轻的领域，可能更好找工作

果然，是金子到哪里都会发光。

后来年轻的威格德森于1980年在以色列理工学院取得学士学位，在短短三年内，又于1983年在普林斯顿大学获得了计算机科学博士学位。他先后在加利福尼亚大学伯克利分校、圣何塞IBM研究院、美国国家数学科学研究所和耶路撒冷希伯来大学担任过职位，2003年成为普林斯顿高等研究院的全职人员。

后来又同时拿到了计算机的诺奖——图灵奖以及数学的诺奖——阿贝尔奖，也成了历史上目前唯一一个达成此成就的人。Wigderson的贡献过于瞩目，以至于有人觉得图灵奖早就颁该给他。

除了突破性的技术贡献外，Wigderson在为人方面也是好评如潮，他被认为是一位受人尊敬的导师和同事，为无数年轻研究人员提供了建议。

此外，Wigderson虽身为一名以色列人，但他坚定地反对以色列对他国领土的侵占，并致力于寻找以色列与巴勒斯坦之间的共同政治解决方案。

他的光辉不仅来源于智慧，还伴随着奉献和道义，这激励着我们所有人。

参考资料