刚刚，2025哥德尔奖出炉！破解30年难题，十年论文摘桂冠

图片

新智元报道  

编辑：KingHZ 定慧

【新智元导读】刚刚，理论计算机年度大奖——2025年哥德尔奖揭晓！康奈尔大学副教授Eshan Chattopadhyay与导师David Zuckerman荣获此奖。

就在刚刚，理论计算机科学界迎来喜讯！

康奈尔大学副教授Eshan Chattopadhyay与导师David Zuckerman，荣获2025年哥德尔奖！

凭借2016年合著的论文《Explicit Two-Source Extractors and Resilient Functions》，他们共享此奖。

图片

论文地址：https://dl.acm.org/doi/10.1145/2897518.2897528

图片

Eshan Chattopadhyay和David Zuckerman

哥德尔奖（Gödel Prize）是一个颁发给理论计算机科学领域杰出论文的年度奖项，由欧洲理论计算机科学协会（EATCS）和美国计算机协会算法和计算理论特别兴趣小组（ACM SIGACT）联合颁发。

图片

哥德尔奖颁奖词：https://www.sigact.org/prizes/g%C3%B6del/citation2025.html

值得一提的是，这篇论文当年还获得了2016年ACM计算理论研讨会最佳论文奖（ACM Symposium on Theory of Computing）。

图片

Chattopadhyay和Zuckerman的论文构造了一种显式的双源提取器（two-source extractor）。

这种提取器只需要多对数级的最小熵（polylogarithmic min-entropy），解决了计算理论中的一个核心难题——

这个问题已经悬而未决将近三十年。

从概念上讲，它可以把两个相互独立但各自并不完美的随机源，合成为一个近似于真正随机的比特输出。

他们的双源提取器由这类鲁棒函数与另外两部分组合而成：

一种带种子的不可篡改提取器（seeded non-malleable extractor）,

一种盲采样器（oblivious sampler）。

在过去，这一结果与鲁棒函数领域没有明显关联，因此这项工作也首次在伪随机性研究的两个子领域之间建立了联系。

图片

Chattopadhyay说：「开始这项工作时，他和David非常乐观——但我们完全不知道我们的方法是否真的会成功」。

从那时起，看到这个领域不断向前发展真是令人惊叹——曾经看似遥远的目标如今已成为积极进展和发现的领域。

我很感激我们的工作能够参与其中，并且很荣幸获得了这样的认可。

Eshan Chattopadhyay研究方向主要集中在理论计算机科学，特别是伪随机性、复杂性理论以及布尔函数分析。

他是康奈尔大学理论研究组的活跃成员，并共同组织系内的计算机科学理论研讨会。

他拥有丰富的教学经验，教授过多门本科和研究生课程，如《算法分析导论》、《布尔函数分析》、《计算复杂性导论》、《计算理论》以及《伪随机性与组合构造》等。

在科研方面，他获得了多项资助，包括斯隆研究奖、NSF CAREER奖和NSF CRII资助。

他的学生多在毕业后进入著名研究机构从事博士后研究。

他也曾发表面向大众的科普文章，并撰写综述文章介绍双源提取器的构造方法。

图片

目前，David Zuckerman在德克萨斯大学奥斯汀分校，担任计算机科学系冠名教授。

他于1987年获得哈佛大学数学学士学位，并曾是普特南研究员（Putnam Fellow），并于1991年获得加州大学伯克利分校的计算机科学博士学位。

1991年至1993年，他在麻省理工学院从事博士后研究，并于1993年秋季在希伯来大学担任博士后研究员。从那时起，他一直在德克萨斯大学工作。

他的研究主要聚焦于伪随机性以及随机性在计算中的作用。他最知名的成果是关于随机性提取器及其应用方面的研究。

此外，他的研究兴趣还包括编码理论、分布式计算、密码学、不可近似性以及计算复杂性的其他领域。

他曾获得多项研究奖项，包括：

2024年美国国家科学院Held奖、2021年FOCS会议颁发的30年时间检验奖、Simons研究员奖、2016年STOC会议的最佳论文奖、ACM会士称号、古根海姆奖学金、帕卡德科学与工程奖学金、斯隆研究奖以及NSF青年研究者奖。

历史上获得者

自1993年以来，该奖项一直持续到现在。

华人学者滕尚华（Shang-Hua Teng）两次获奖，分别为2008和2015。

图片

滕尚华

此外，2021年， 华人学者蔡进一（Jin-Yi Cai）（下图左）和陈汐(Xi Chen)（下图右），因在约束满足问题的计数复杂性分类方面的工作获此殊荣。

图片

目前，共有6位学者两次获奖，其他五位分别是Shafi Goldwasser（1993,2001），Sanjeev Arora（2001,2010），Johan Håstad（1994,2011），Mario Szegedy（2001, 2005），Daniel Spielman（2008， 2015）。

其中，Shafi Goldwasser是1993年首届哥德尔奖女性得主。

2012年，她与1993年Silvio Micali共同获得图灵奖（Turing Award）。

图片

以下为1993年-2024年，获得者名单、原因和获奖工作出版年份。

图片

图片

图片

奖项介绍

哥德尔奖（Gödel Prize）是为表彰在理论计算机科学领域中杰出论文而设立的奖项，由欧洲理论计算机科学协会（EATCS）与美国计算机协会算法与计算理论特别兴趣小组（ACM SIGACT）共同赞助。

图片

该奖项每年颁发一次，颁奖仪式轮流在EATCS国际自动机、语言与程序设计讨论会（ICALP）和ACM理论计算年会（STOC）上举行。

图片

该奖项以库尔特·哥德尔（Kurt Gödel）的名字命名，以表彰他在数学逻辑领域的重大贡献，以及他对后来被称为「P与NP问题」的兴趣——

这一兴趣可从他在冯·诺伊曼去世前不久写给对方的一封信中得知。

哥德尔奖的奖金为5000美元。

图片

哥德尔奖奖章

哥德尔

哥德尔奖是为纪念库尔特·哥德尔而命名的。

图片

库尔特·哥德尔（1906——1978）出生于奥匈帝国的美国数学家、逻辑学家和哲学家，维也纳学派（维也纳小组）的成员。

哥德尔是二十世纪最伟大的逻辑学家之一，其最杰出的贡献是哥德尔不完备定理和连续统假设的相对协调性证明。

约翰·冯·诺依曼曾经评价他：

库尔特·哥德尔在现代逻辑学上的成就是独一无二且意义重大的——

确切地说，这不仅仅是一座纪念碑，而是一个里程碑。

其影响力在广阔的空间和时间范围内都将持续存在。

……有了哥德尔的成就，逻辑学的主题的确彻底改变了它的本质和可能性。

1933年，哥德尔首次前往美国，在那里他遇到了阿尔伯特·爱因斯坦，并成为好友。

哥德尔于1961年当选为美国哲学学会会士，1968年当选为英国皇家学会外籍会员。

参考资料：

https://www.sigact.org/prizes/g%C3%B6del.html

https://en.wikipedia.org/wiki/G%C3%B6del_Prize

https://blog.computationalcomplexity.org/2025/06/the-new-godel-prize-winner-tastes-great.html

https://cis.cornell.edu/chattopadhyay-awarded-godel-prize-landmark-paper