2023 年图灵奖,刚刚揭晓!
获得这届「计算机界诺贝尔奖」——ACM A.M.图灵奖的,就是普林斯顿高等研究院数学学院的教授 Avi Wigderson。
表彰的是 Wigderson 在计算理论领域的开创性贡献,特别是他对计算中随机性角色的重新定义,以及他在理论计算机科学领域数十年的引领。
Wigderson是普林斯顿高级研究院数学学院的Herbert H. Maass教授。
他在计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算、组合学和图论等领域均有突出贡献,并且在理论计算机科学与数学及科学的交叉领域中,也具有重要影响。
这已不是威格德森首次斩获大奖,2019年,他就凭借在随机计算、密码学、并行计算等计算机科学基础领域做出的贡献获得高德纳奖——计算机科学界极富盛誉的奖项之一。2021年,他又与匈牙利厄特沃什·罗兰大学教授拉兹洛·洛瓦兹(LászlóLovász)一同获得国际数学界“三大奖”之一的阿贝尔奖。
在得知获图灵奖的消息后,今年67岁的威格德森在接受《自然》采访时表示“非常高兴,没想到会获奖”。他认为自己已经收获了足够多的爱和赞赏,不需要其他奖项了。
Avi Wigderson 在 UC Berkeley 的图书馆
值得一提的是,他还在5个月前来到清华叉院做客,对当下大语言模型的发展表达了自己的看法。
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.258590
Wigderson这三篇论文的影响远远超出了随机性和去随机化领域。这些论文中的观点随后被应用于理论计算机科学的许多领域,并激发了该领域多位领军人物发表具有影响力的论文。
目前,Wigderson与Omer Reingold、Salil Vadhan、Michael Capalbo合作,仍然在计算随机性的广泛领域开展工作,在一篇论文中首次提出了扩展图的高效组合构造(https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf)。扩展图是一种稀疏图,具有很强的连通性,在数学和理论计算机科学领域都有许多重要应用。
除了在随机性方面的研究之外,Wigderson还是理论计算机科学其他几个领域的知识领袖,包括多验证器交互式证明、密码学和电路复杂性。
图灵奖是ACM于1966年设立的奖项,专门奖励对计算机事业作出重要贡献的个人,有着「计算机界诺贝尔奖」之称,奖金为100万美元,由谷歌赞助。图灵奖的名称取自英国数学家艾伦·图灵(Alan M. Turing),他奠定了计算机的数学基础,也阐述了其局限性。
来源:机器之心pro,量子位等,爱科会易仅用于学术交流。
2023 年图灵奖,刚刚揭晓!
获得这届「计算机界诺贝尔奖」——ACM A.M.图灵奖的,就是普林斯顿高等研究院数学学院的教授 Avi Wigderson。
表彰的是 Wigderson 在计算理论领域的开创性贡献,特别是他对计算中随机性角色的重新定义,以及他在理论计算机科学领域数十年的引领。
Wigderson是普林斯顿高级研究院数学学院的Herbert H. Maass教授。
他在计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算、组合学和图论等领域均有突出贡献,并且在理论计算机科学与数学及科学的交叉领域中,也具有重要影响。
这已不是威格德森首次斩获大奖,2019年,他就凭借在随机计算、密码学、并行计算等计算机科学基础领域做出的贡献获得高德纳奖——计算机科学界极富盛誉的奖项之一。2021年,他又与匈牙利厄特沃什·罗兰大学教授拉兹洛·洛瓦兹(LászlóLovász)一同获得国际数学界“三大奖”之一的阿贝尔奖。
在得知获图灵奖的消息后,今年67岁的威格德森在接受《自然》采访时表示“非常高兴,没想到会获奖”。他认为自己已经收获了足够多的爱和赞赏,不需要其他奖项了。
Avi Wigderson 在 UC Berkeley 的图书馆
值得一提的是,他还在5个月前来到清华叉院做客,对当下大语言模型的发展表达了自己的看法。
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.258590
Wigderson这三篇论文的影响远远超出了随机性和去随机化领域。这些论文中的观点随后被应用于理论计算机科学的许多领域,并激发了该领域多位领军人物发表具有影响力的论文。
目前,Wigderson与Omer Reingold、Salil Vadhan、Michael Capalbo合作,仍然在计算随机性的广泛领域开展工作,在一篇论文中首次提出了扩展图的高效组合构造(https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf)。扩展图是一种稀疏图,具有很强的连通性,在数学和理论计算机科学领域都有许多重要应用。
除了在随机性方面的研究之外,Wigderson还是理论计算机科学其他几个领域的知识领袖,包括多验证器交互式证明、密码学和电路复杂性。
图灵奖是ACM于1966年设立的奖项,专门奖励对计算机事业作出重要贡献的个人,有着「计算机界诺贝尔奖」之称,奖金为100万美元,由谷歌赞助。图灵奖的名称取自英国数学家艾伦·图灵(Alan M. Turing),他奠定了计算机的数学基础,也阐述了其局限性。
来源:机器之心pro,量子位等,爱科会易仅用于学术交流。