今日应用
今日话题
Avi Wigderson获2023年图灵奖:重塑人们对随机性在计算中作用的理解
重点标签 理论计算机科学、随机性、图灵奖、算法、Wigderson
文章摘要
理论计算机科学关注计算领域的数学基础,提出问题如“这个问题是否可以通过计算来解决?”以及“如果可以通过计算解决,需要多少时间和其他资源?”等问题。该领域还探讨有效算法的设计,影响我们对自然法则的理解。尽管理论计算机科学通常不直接涉及实际应用,但该领域的研究突破已导致多个领域的进步,包括密码学、计算生物学、网络设计、机器学习和量子计算。
随机性对计算至关重要,因为计算机是确定性系统,而我们生活的世界充满了随机事件。计算机科学家通过允许算法在计算过程中进行随机选择来提高效率。Wigderson 在理解随机性和伪随机性在计算中的作用方面做出了基础性贡献。他与同事合作,发表了关于以难度换取随机性的高影响力作品,证明了在标准计算假设下,每个概率多项式时间算法都可以被有效地去随机化。这些论文的思想已应用于理论计算机科学的许多领域。
除了在随机性领域的工作外,Wigderson 还在多证人交互证明、密码学和电路复杂性等领域发挥知识领袖作用。他还是一位受人尊敬的导师和同事,为许多年轻研究者提供建议。Wigderson 获得的荣誉包括阿贝尔奖、IMU算盘奖、Donald E. Knuth奖等。他是ACM院士,也是美国国家科学院和美国艺术与科学院的成员。
文章来源
原文地址: 点我阅读全文
原文作者: AIGC最前线
© 版权声明
文章版权归作者所有,未经允许请勿转载。
相关文章
暂无评论...