就在剛剛，理論計算機(jī)科學(xué)界迎來喜訊！

康奈爾大學(xué)副教授Eshan Chattopadhyay與導(dǎo)師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）是一個頒發(fā)給理論計算機(jī)科學(xué)領(lǐng)域杰出論文的年度獎項，由歐洲理論計算機(jī)科學(xué)協(xié)會（EATCS）和美國計算機(jī)協(xié)會算法和計算理論特別興趣小組（ACM SIGACT）聯(lián)合頒發(fā)。

哥德爾獎頒獎詞：https://www.sigact.org/prizes/g%C3%B6del/citation2025.html

值得一提的是，這篇論文當(dāng)年還獲得了2016年ACM計算理論研討會最佳論文獎（ACM Symposium on Theory of Computing）。

Chattopadhyay和Zuckerman的論文構(gòu)造了一種顯式的雙源提取器（two-source extractor）。

這種提取器只需要多對數(shù)級的最小熵（polylogarithmic min-entropy），解決了計算理論中的一個核心難題——

這個問題已經(jīng)懸而未決將近三十年。

從概念上講，它可以把兩個相互獨(dú)立但各自并不完美的隨機(jī)源，合成為一個近似于真正隨機(jī)的比特輸出。

他們的雙源提取器由這類魯棒函數(shù)與另外兩部分組合而成：

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

一種盲采樣器（oblivious sampler）。

在過去，這一結(jié)果與魯棒函數(shù)領(lǐng)域沒有明顯關(guān)聯(lián)，因此這項工作也首次在偽隨機(jī)性研究的兩個子領(lǐng)域之間建立了聯(lián)系。

Chattopadhyay說：「開始這項工作時，他和David非常樂觀——但我們完全不知道我們的方法是否真的會成功」。

從那時起，看到這個領(lǐng)域不斷向前發(fā)展真是令人驚嘆——曾經(jīng)看似遙遠(yuǎn)的目標(biāo)如今已成為積極進(jìn)展和發(fā)現(xiàn)的領(lǐng)域。

我很感激我們的工作能夠參與其中，并且很榮幸獲得了這樣的認(rèn)可。

Eshan Chattopadhyay研究方向主要集中在理論計算機(jī)科學(xué)，特別是偽隨機(jī)性、復(fù)雜性理論以及布爾函數(shù)分析。

他是康奈爾大學(xué)理論研究組的活躍成員，并共同組織系內(nèi)的計算機(jī)科學(xué)理論研討會。

他擁有豐富的教學(xué)經(jīng)驗(yàn)，教授過多門本科和研究生課程，如《算法分析導(dǎo)論》、《布爾函數(shù)分析》、《計算復(fù)雜性導(dǎo)論》、《計算理論》以及《偽隨機(jī)性與組合構(gòu)造》等。

在科研方面，他獲得了多項資助，包括斯隆研究獎、NSF CAREER獎和NSF CRII資助。

他的學(xué)生多在畢業(yè)后進(jìn)入著名研究機(jī)構(gòu)從事博士后研究。

他也曾發(fā)表面向大眾的科普文章，并撰寫綜述文章介紹雙源提取器的構(gòu)造方法。

目前，David Zuckerman在德克薩斯大學(xué)奧斯汀分校，擔(dān)任計算機(jī)科學(xué)系冠名教授。

他于1987年獲得哈佛大學(xué)數(shù)學(xué)學(xué)士學(xué)位，并曾是普特南研究員（Putnam Fellow），并于1991年獲得加州大學(xué)伯克利分校的計算機(jī)科學(xué)博士學(xué)位。

1991年至1993年，他在麻省理工學(xué)院從事博士后研究，并于1993年秋季在希伯來大學(xué)擔(dān)任博士后研究員。從那時起，他一直在德克薩斯大學(xué)工作。

他的研究主要聚焦于偽隨機(jī)性以及隨機(jī)性在計算中的作用。他最知名的成果是關(guān)于隨機(jī)性提取器及其應(yīng)用方面的研究。

此外，他的研究興趣還包括編碼理論、分布式計算、密碼學(xué)、不可近似性以及計算復(fù)雜性的其他領(lǐng)域。

他曾獲得多項研究獎項，包括：

2024年美國國家科學(xué)院Held獎、2021年FOCS會議頒發(fā)的30年時間檢驗(yàn)獎、Simons研究員獎、2016年STOC會議的最佳論文獎、ACM會士稱號、古根海姆獎學(xué)金、帕卡德科學(xué)與工程獎學(xué)金、斯隆研究獎以及NSF青年研究者獎。

歷史上獲得者

自1993年以來，該獎項一直持續(xù)到現(xiàn)在。

華人學(xué)者滕尚華（Shang-Hua Teng）兩次獲獎，分別為2008和2015。

滕尚華

此外，2021年， 華人學(xué)者蔡進(jìn)一（Jin-Yi Cai）（下圖左）和陳汐(Xi Chen)（下圖右），因在約束滿足問題的計數(shù)復(fù)雜性分類方面的工作獲此殊榮。

目前，共有6位學(xué)者兩次獲獎，其他五位分別是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）是為表彰在理論計算機(jī)科學(xué)領(lǐng)域中杰出論文而設(shè)立的獎項，由歐洲理論計算機(jī)科學(xué)協(xié)會（EATCS）與美國計算機(jī)協(xié)會算法與計算理論特別興趣小組（ACM SIGACT）共同贊助。

該獎項每年頒發(fā)一次，頒獎儀式輪流在EATCS國際自動機(jī)、語言與程序設(shè)計討論會（ICALP）和ACM理論計算年會（STOC）上舉行。

該獎項以庫爾特·哥德爾（Kurt G?del）的名字命名，以表彰他在數(shù)學(xué)邏輯領(lǐng)域的重大貢獻(xiàn)，以及他對后來被稱為「P與NP問題」的興趣——

這一興趣可從他在馮·諾伊曼去世前不久寫給對方的一封信中得知。

哥德爾獎的獎金為5000美元。

哥德爾獎獎?wù)?/span>

哥德爾

哥德爾獎是為紀(jì)念庫爾特·哥德爾而命名的。

庫爾特·哥德爾（1906——1978）出生于奧匈帝國的美國數(shù)學(xué)家、邏輯學(xué)家和哲學(xué)家，維也納學(xué)派（維也納小組）的成員。

哥德爾是二十世紀(jì)最偉大的邏輯學(xué)家之一，其最杰出的貢獻(xiàn)是哥德爾不完備定理和連續(xù)統(tǒng)假設(shè)的相對協(xié)調(diào)性證明。

約翰·馮·諾依曼曾經(jīng)評價他：

庫爾特·哥德爾在現(xiàn)代邏輯學(xué)上的成就是獨(dú)一無二且意義重大的——

確切地說，這不僅僅是一座紀(jì)念碑，而是一個里程碑。

其影響力在廣闊的空間和時間范圍內(nèi)都將持續(xù)存在。

……有了哥德爾的成就，邏輯學(xué)的主題的確徹底改變了它的本質(zhì)和可能性。

1933年，哥德爾首次前往美國，在那里他遇到了阿爾伯特·愛因斯坦，并成為好友。

哥德爾于1961年當(dāng)選為美國哲學(xué)學(xué)會會士，1968年當(dāng)選為英國皇家學(xué)會外籍會員。