2023年图灵奖揭晓！普林斯顿数学教授，成史上首位阿贝尔奖双料获奖者

1,262 0 0

文章摘要

【关键词】 图灵奖、Avi Wigderson、随机性、伪随机性、理论计算机

Avi Wigderson，普林斯顿高等研究院数学学院的教授，因其在计算理论领域的开创性贡献而荣获2023年图灵奖。他的研究重新定义了计算中随机性的角色，并在理论计算机科学领域有着长期的引领作用。Wigderson也是历史上第一位同时获得图灵奖和阿贝尔奖的人，阿贝尔奖是数学领域的最高荣誉。

Wigderson在计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算、组合学和图论等多个领域均有显著成就。他的研究对理论计算机科学与数学及科学的交叉领域产生了重要影响。他的工作包括高效构造展开图，这些图在数学和理论计算机科学中有广泛应用。

Wigderson对计算中的随机性和伪随机性的研究具有开创性。他与同事合作证明了在一些广泛认可的计算假设下，所有的概率多项式时间算法都可以被有效转化为确定性算法，表明高效的计算并不依赖于随机性。他的三篇极具影响力的论文分别介绍了新型伪随机发生器、在亚指数时间内模拟有限错误概率多项式时间算法的方法，以及难度与随机性之间的最优权衡。

除了随机性研究，Wigderson还在多证明者交互式证明、密码学和电路复杂度等多个理论计算机科学领域发挥了重要的领导作用。他作为导师和同事，以亲和力、热情和慷慨著称，吸引了众多青年学者投身理论计算机科学领域。

Wigderson对计算复杂性理论的兴趣源于对问题是否有解决方案的好奇。他在海法大学开始了大学生涯，最初主修数学，后转向计算机科学。他的早期工作探讨了零知识交互证明的概念，即在不展示证明过程的情况下让人相信一个数学命题已经得到了证明。他与其他学者一起进一步发展了这一理论，证明了如果一个命题可以被证明，那么它也可以有一个零知识证明。

Wigderson的研究将计算难度与随机性相联系，发现对于许多难题，概率算法优于确定性算法。他与Richard Karp合作，将随机性的思想应用于计算上极其困难的问题，并成功将难题的随机算法转化为确定性算法。他的研究表明，随机性总是可以被消除，并且确定性算法可以使用伪随机序列。

Wigderson指出，随机性已经成为复杂性理论中的一个强大工具，但它非常难以捉摸。他认为，任何自然过程都可以被视为一种演化的计算过程，因此可以从计算的角度来研究它。Wigderson曾获得哥德尔奖、ACM Fellow荣誉，并在2019年获得了高德纳奖，以表彰他对计算机科学和数学理论的贡献。