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

康奈爾大學(xué)副教授Eshan Chattopadhyay與導(dǎo)師David Zuckerman，榮獲2025年哥德?tīng)柂?jiǎng)！

憑借2016年合著的論文《Explicit Two-Source Extractors and Resilient Functions》，他們共享此獎(jiǎng)。

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

Eshan Chattopadhyay和David Zuckerman

哥德?tīng)柂?jiǎng)（G?del Prize）是一個(gè)頒發(fā)給理論計(jì)算機(jī)科學(xué)領(lǐng)域杰出論文的年度獎(jiǎng)項(xiàng)，由歐洲理論計(jì)算機(jī)科學(xué)協(xié)會(huì)（EATCS）和美國(guó)計(jì)算機(jī)協(xié)會(huì)算法和計(jì)算理論特別興趣小組（ACM SIGACT）聯(lián)合頒發(fā)。

哥德?tīng)柂?jiǎng)?lì)C獎(jiǎng)詞：https://www.sigact.org/prizes/g%C3%B6del/citation2025.html

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

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

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

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

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

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

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

一種盲采樣器（oblivious sampler）。

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

Chattopadhyay說(shuō)：「開(kāi)始這項(xiàng)工作時(shí)，他和David非常樂(lè)觀——但我們完全不知道我們的方法是否真的會(huì)成功」。

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

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

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

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

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

在科研方面，他獲得了多項(xiàng)資助，包括斯隆研究獎(jiǎng)、NSF CAREER獎(jiǎng)和NSF CRII資助。

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

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

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

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

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

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

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

他曾獲得多項(xiàng)研究獎(jiǎng)項(xiàng)，包括：

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

歷史上獲得者

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

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

滕尚華

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

目前，共有6位學(xué)者兩次獲獎(jiǎng)，其他五位分別是Shafi Goldwasser（1993,2001），Sanjeev Arora（2001,2010），Johan H?stad（1994,2011），Mario Szegedy（2001, 2005），Daniel Spielman（2008， 2015）。

其中，Shafi Goldwasser是1993年首屆哥德?tīng)柂?jiǎng)女性得主。

2012年，她與1993年Silvio Micali共同獲得圖靈獎(jiǎng)（Turing Award）。

以下為1993年-2024年，獲得者名單、原因和獲獎(jiǎng)工作出版年份。

獎(jiǎng)項(xiàng)介紹

哥德?tīng)柂?jiǎng)（G?del Prize）是為表彰在理論計(jì)算機(jī)科學(xué)領(lǐng)域中杰出論文而設(shè)立的獎(jiǎng)項(xiàng)，由歐洲理論計(jì)算機(jī)科學(xué)協(xié)會(huì)（EATCS）與美國(guó)計(jì)算機(jī)協(xié)會(huì)算法與計(jì)算理論特別興趣小組（ACM SIGACT）共同贊助。

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

該獎(jiǎng)項(xiàng)以庫(kù)爾特·哥德?tīng)枺↘urt G?del）的名字命名，以表彰他在數(shù)學(xué)邏輯領(lǐng)域的重大貢獻(xiàn)，以及他對(duì)后來(lái)被稱為「P與NP問(wèn)題」的興趣——

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

哥德?tīng)柂?jiǎng)的獎(jiǎng)金為5000美元。

哥德?tīng)柂?jiǎng)獎(jiǎng)?wù)?/span>

哥德?tīng)?/span>

哥德?tīng)柂?jiǎng)是為紀(jì)念庫(kù)爾特·哥德?tīng)柖摹?/span>

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

哥德?tīng)柺嵌兰o(jì)最偉大的邏輯學(xué)家之一，其最杰出的貢獻(xiàn)是哥德?tīng)柌煌陚涠ɡ砗瓦B續(xù)統(tǒng)假設(shè)的相對(duì)協(xié)調(diào)性證明。

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

庫(kù)爾特·哥德?tīng)栐诂F(xiàn)代邏輯學(xué)上的成就是獨(dú)一無(wú)二且意義重大的——

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

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

……有了哥德?tīng)柕某删停壿媽W(xué)的主題的確徹底改變了它的本質(zhì)和可能性。

1933年，哥德?tīng)柺状吻巴绹?guó)，在那里他遇到了阿爾伯特·愛(ài)因斯坦，并成為好友。

哥德?tīng)栍?961年當(dāng)選為美國(guó)哲學(xué)學(xué)會(huì)會(huì)士，1968年當(dāng)選為英國(guó)皇家學(xué)會(huì)外籍會(huì)員。