文章摘要
【关 键 词】 理论计算机、哥德尔奖、双源提取器、伪随机性、复杂性理论
康奈尔大学副教授Eshan Chattopadhyay与导师David Zuckerman荣获2025年哥德尔奖，表彰他们在理论计算机科学领域的杰出贡献。他们的获奖论文《Explicit Two-Source Extractors and Resilient Functions》发表于2016年，并曾获得同年ACM计算理论研讨会最佳论文奖。这篇论文提出了一种显式的双源提取器，解决了计算理论中一个悬而未决近三十年的核心难题。该提取器只需要多对数级的最小熵，能够将两个相互独立但各自不完美的随机源合成为近似于真正随机的比特输出。
双源提取器的构造由三部分组成：一种带种子的不可篡改提取器、一种盲采样器以及鲁棒函数。这项研究首次在伪随机性研究的两个子领域之间建立了联系，推动了相关领域的进一步发展。Chattopadhyay表示，尽管他们在研究初期对方法的可行性并不确定，但最终取得的成果令人振奋，并且为后续研究开辟了新的方向。
Eshan Chattopadhyay的研究方向主要集中在理论计算机科学，特别是伪随机性、复杂性理论以及布尔函数分析。他不仅是康奈尔大学理论研究组的活跃成员，还教授多门本科和研究生课程，并在科研方面获得了多项资助，包括斯隆研究奖和NSF CAREER奖。他的学生毕业后多进入著名研究机构从事博士后研究，进一步推动了理论计算机科学的发展。
David Zuckerman现任德克萨斯大学奥斯汀分校计算机科学系冠名教授，研究聚焦于伪随机性以及随机性在计算中的作用。他最知名的成果是关于随机性提取器及其应用的研究，曾获得多项研究奖项，包括2024年美国国家科学院Held奖和2021年FOCS会议颁发的30年时间检验奖。他的研究兴趣还涵盖编码理论、分布式计算、密码学等领域，为理论计算机科学的发展做出了重要贡献。
哥德尔奖是理论计算机科学领域的最高荣誉之一，由欧洲理论计算机科学协会与美国计算机协会算法与计算理论特别兴趣小组联合颁发。该奖项以库尔特·哥德尔的名字命名，旨在表彰他在数学逻辑领域的重大贡献，特别是他对“P与NP问题”的兴趣。自1993年设立以来，哥德尔奖已表彰了多位杰出学者，其中包括华人学者滕尚华和蔡进一等人。
库尔特·哥德尔是二十世纪最伟大的逻辑学家之一，其最杰出的贡献是哥德尔不完备定理和连续统假设的相对协调性证明。约翰·冯·诺依曼曾评价哥德尔的成就为“逻辑学主题的本质和可能性的彻底改变”。哥德尔的研究不仅对数学和逻辑学产生了深远影响，也为理论计算机科学的发展奠定了重要基础。
原文和模型
【原文链接】 阅读原文 [ 1719字 | 7分钟 ]
【原文作者】 新智元
【摘要模型】 deepseek-v3
【摘要评分】 ★★★★☆
相关文章
