新智元報道

　　編輯：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