2025年哥德爾獎出爐！破解30年難題，十年論文摘桂冠

剛剛，理論電腦年度大獎——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

哥德爾獎（Gödel Prize）是一個頒發給理論電腦科學領域傑出論文的年度獎項，由歐洲理論電腦科學協會（EATCS）和美國電腦協會演算法和計算理論特別興趣小組（ACM SIGACT）聯合頒發。

值得一提的是，這篇論文當年還獲得了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年當選為英國皇家學會外籍會員。 (新智元)