阐明算法随机性的数学家在计算领域获得最高奖

这2023 图灵奖——相当于计算机界的诺贝尔奖——已经授予了数学家阿维·维格德森以表彰他对计算机科学的开创性和广泛适用性的贡献。该荣誉附带 100 万美元的奖金。

在他长达数十年的职业生涯中，这位67岁的高等研究院教授关心的是一个问题是否可以解决，而不是答案可能是什么——这是被称为理论计算机科学的专业的一部分。

“据我们所知，对于我们面临并试图解决的每一个问题，我们不能排除它有一种可以解决它的算法，”Wigderson说广达杂志的斯蒂芬·奥恩斯。“这对我来说是最有趣的问题。”

他工作的核心是随机性和不可预测性。计算机倾向于以可预测的方式工作，遵循确定的模式。但从1980年代初的研究开始，Wigderson发现，在某些情况下，在特定算法中添加未知数或随机性可以更容易、更快速地找到解决方案。相反，他发现可以从其他算法中去除随机性，从而更容易得出解决方案。

他研究和完善随机性与问题的难度和可解决性之间的关系，对现代计算产生了深远的影响。

“在计算机科学的任何领域工作，如果不与Avi的工作有交集，就很难。Madhu， 苏丹哈佛大学的计算机科学家过去曾与Wigderson合作进行研究，他说广达杂志.“在任何地方，你都能找到非常深刻的见解。”

雅尼斯·约阿尼迪斯，颁发图灵奖的组织计算机协会主席称威格德森是“理论计算机科学中高耸的智力力量”。陈述本周。

例如，他的贡献帮助研究人员更好地理解了该领域最著名的未经证实的猜想之一，称为P 与 NP 问题.它问：如果一个问题的解决方案很容易验证，那么问题本身是否容易解决？该猜想表明，计算机的简单问题和困难问题根本不同。在随机性方面，威格德森帮助澄清特定证据并发现简单和困难问题相同的独特实例。

Wigderson还写了关于如何将理论计算中的概念应用于各种自然和人为过程的文章——随机性可以在解决难题方面发挥作用，例如寻找治愈癌症的方法。《纽约时报》' 凯德·梅斯。随机性支配着世界上的许多过程，从股票市场到互联网八卦，再到疾病的传播和培养皿中细菌的活动。

因此，Wigderson工作的影响已经远远超出了计算机科学。密码学、云计算和区块链开发的现代领域都充满了Wigderson的原理和发现。

例如，他在随机性和算法方面的工作有助于推进零知识协议，这是计算机安全中的一种关键方法，允许在各方之间传输和确认敏感信息。在最简单的工作中，一方能够证明一个条件对另一方来说是真实的，而无需透露任何其他细节。随机、唯一的数字密钥还有助于保护在线数据。

这门学科最近在数学领域得到了认可，这证明了描述和利用随机性如何跨越多个领域。2024年阿贝尔奖，世界数学最高奖项，被送给法国数学家米歇尔·塔拉格兰德上个月，他在随机系统方面取得了进步，这有助于更精确地模拟随机变量。

在各种其他奖项中，威格德森荣获 2021 年阿贝尔奖与数学家拉斯洛·洛瓦斯（László Lovász）一起，帮助将数学与计算机科学联系起来。这一新荣誉使威格德森成为唯一一位同时获得图灵奖和阿贝尔奖的人。

“在过去40年里，Avi对计算理论的影响是首屈一指的，”奥德·戈德赖希以色列魏茨曼科学研究所（Weizmann Institute of Science）的计算机科学教授说新科学家的亚历克斯·威尔金斯。“他所贡献的领域的多样性令人惊叹。”

尽管他在可预测性方面取得了所有成就，但威格德森没有解决的一个过程是他自己的图灵奖公告。

“[图灵]委员会欺骗了我，让我相信我们将就合作进行一些对话，”威格德森说新科学家.“当我放大时，整个委员会都在那里，他们告诉我。我很兴奋、惊讶和高兴。