Avi Wigderson 获图灵奖: 在随机性改进算法方面做出了重大贡献

聊点云上事儿2024-04-11 13:04:42  70

Avi Wigderson 喜捧 2023 年图灵奖,他在理解随机性如何塑造和改进计算机算法方面做出了重大贡献。

数学家 Avi Wigderson 喜捧 2023 年图灵奖,该奖项常常被称为计算机领域的诺贝尔奖,他在理解随机性如何塑造和改进计算机算法方面做出了贡献。

Wigderson 对自己获得这个奖项颇为惊讶,他还因在计算机科学方面的数学贡献在 2021 年获得了著名的阿贝尔奖(Abel prize)。

他说:“(图灵奖)委员会骗了我,让我以为我们是要讨论合作问题。等我定睛细看时,才发觉整个委员会都到场了,他们告诉了我这则喜讯。我是激动、惊讶又开心。”

计算机在硬件层面以一种可预测的方式工作,但这可能使计算机难以为现实世界的问题建模,实际问题通常具有随机性和不可预测性。在新泽西州普林斯顿高级研究所工作的Wigderson 在其长达数十年的职业生涯中已经证明,计算机也可以利用它们运行的算法中的随机性。

Wigderson和同事在 20 世纪 80 年代发现,通过在一些算法中插入随机性,他们可以使算法更容易、更快速地解决问题,但当时还不清楚这种技术的适用性有多广。他说:“我们想知道这种随机性是否必要,或者如果你够聪明,也许你能设法摆脱这种随机性。”

Wigderson 最重要的发现之一是,阐明了问题类型(就解决难度而言)与随机性之间的关系。他还表明,可以将某些含有随机性且难以运行的算法设计成具有确定性或非随机性,从而更容易运行。

这些发现帮助了计算机科学家们更清楚地理解计算机科学界最著名的未经证实的猜想之一,即“P≠NP”。该猜想提出,计算机要解决的简单问题和困难问题存在根本上的不同。利用随机性,Wigderson 发现了这两类问题其实一样的特殊情况。

Wigderson 在 20 世纪 80 年代开始探究随机性与计算机之间的关系,那时互联网还没有出现,让他沉迷于研究工作的是求知欲,而不是如何利用成果谋私利。他说:“我是非常不切实际的人。我其实不是受奖金的激励。”

然而,他的想法对于从密码学到云计算的许多现代计算应用都很重要。以色列魏茨曼科学研究所的 Oded Goldreich 说:“在过去的 40 年里,Avi 对计算理论的影响首屈一指。他为众多的不同领域都做出了贡献。”

Wigderson 的思想现在得到了广泛应用,他与 Goldreich 及其他人一起研究的零知识证明就得到了意想不到的应用,零知识证明详述了在不泄露信息本身的情况下验证信息的方法。这些方法是当今加密货币和区块链的基础,是在不同用户之间建立信任的一种方式。

虽然计算理论在 Wigderson 的职业生涯期间取得了巨大的进步,但他表示,这个领域仍然充满了值得关注、仍未解决的问题。他说:“你无法想象我在从事的这个领域搞研究工作有多开心,面对的是一大堆需要开动脑筋的问题。”

Wigderson 因图灵奖而领到 100 万美元的奖金。

转载此文是出于传递更多信息目的。若来源标注错误或侵犯了您的合法权益,请与本站联系,我们将及时更正、删除、谢谢。
https://www.414w.com/read/209691.html
0
最新回复(0)