2023 · 理论与算法

随机性究竟能帮多少忙？

复杂性理论将随机选择与计算最深层的边界连接起来。

阿维·威格德森

2023图灵奖

视觉指南

奖项，化为图解

阅读图解文字

这些联系表明，算法设计、计算困难性与伪随机性属于同一个理论图景。

伪随机性针对特定观察者或检验，并不等同于物理随机性。

01 · 核心想法

阿维·威格德森重塑了人们对计算中随机性的理解，并为理论计算机科学作出广泛贡献。随机算法可能很强大，但能否用确定性构造替代随机选择？伪随机性与去随机化研究，将这个问题与其他计算问题的难度联系起来。

这些联系表明，算法设计、计算困难性与伪随机性属于同一个理论图景。

02 · 人物

阿维·威格德森研究高效计算的能力与局限，尤其关注随机性的作用。他把计算复杂性与密码学、交互式证明以及用确定性方法替代随机选择的研究联系起来。他在普林斯顿高等研究院推动对算法的广泛数学理解。图灵奖表彰其基础成果，以及这些思想对理论计算机科学的影响。

03 · 延伸阅读

本站原创讲解依据官方获奖记录。领域标签用于编辑导航。