美國計(jì)算機(jī)協(xié)會演算法與計(jì)算理論特別興趣小組 (ACM SIGACT) 周一 (9 日) 宣布,2025 年哥德爾獎授予康乃爾大學(xué)副教授 Eshan Chattopadhyay 與導(dǎo)師 David Zuckerman,兩人憑藉 2016 年合著的經(jīng)典論文《顯式雙源提取器與彈性函數(shù)》(Explicit Two-Source Extractors and Resilient Functions),共同摘得這一理論計(jì)算機(jī)領(lǐng)域的最高榮譽(yù)。
中國 AI 媒體《新智元》報(bào)導(dǎo),在論文中,兩位學(xué)者他們構(gòu)造了一種「顯式雙源提取器」,只需兩個(gè)獨(dú)立但「不完美」的隨機(jī)源(每個(gè)隨機(jī)源的最小熵僅為多對數(shù)級,即 polylogarithmic min-entropy),就能將其合成為一個(gè)近似於真正隨機(jī)的比特輸出,解決了在理論計(jì)算機(jī)科學(xué)領(lǐng)域懸而未決近三十年的問題,是偽隨機(jī)性研究的核心挑戰(zhàn)之一。
他們的雙源提取器由這類魯棒函數(shù)與另外兩部分組合而成,一個(gè)是帶種子的不可篡改提取器 (seeded non-malleable extractor) 跟盲採樣器(oblivious sampler)。
簡單來說,隨機(jī)來源的「不完美」如同現(xiàn)實(shí)中拋一枚略有偏差的硬幣,結(jié)果雖不確定,但存在微小的統(tǒng)計(jì)規(guī)律,而雙源提取器的作用就像一臺「隨機(jī)淨(jìng)化機(jī)」,能將兩枚有偏差的硬幣的結(jié)果融合,最終輸出接近絕對隨機(jī)的比特序列。更關(guān)鍵的是,這項(xiàng)成果首次在偽隨機(jī)性的兩個(gè)子領(lǐng)域(穩(wěn)健函數(shù)與隨機(jī)取樣)之間架起了橋樑。
對此 Chattopadhyay 回憶道:「我們開始這項(xiàng)工作時(shí)充滿樂觀,但完全沒想到方法真的會成功。如今看到領(lǐng)域因這項(xiàng)工作持續(xù)發(fā)展,我深感榮幸。」
Chattopadhyay 現(xiàn)為康乃爾大學(xué)理論研究小組活躍成員,主要研究方向包括偽隨機(jī)性、複雜性理論及布林函數(shù)分析。他不僅教授《演算法分析導(dǎo)論》、《計(jì)算複雜性導(dǎo)論》等大學(xué)部課程,也指導(dǎo)多位學(xué)生進(jìn)入頂尖機(jī)構(gòu)從事博士後研究,並透過科普文章向大眾介紹雙源提取器等技術(shù)。此前,他已斬獲斯隆研究獎、NSF CAREER 獎等多項(xiàng)學(xué)術(shù)榮譽(yù)。
Zuckerman 則是德州大學(xué)奧斯丁分校電腦科學(xué)系冠名教授,研究領(lǐng)域涵蓋偽隨機(jī)性、編碼理論、分散式計(jì)算及密碼學(xué)等。他的學(xué)術(shù)履歷堪稱「獎項(xiàng)收割機(jī)」,去年獲美國國家科學(xué)院 Held 獎、2021 年獲 FOCS 會議 30 年時(shí)間檢驗(yàn)獎、2016 年獲 STOC 最佳論文獎,更於 1991 年獲普特南研究員 (Putnam Fellow) 稱號。自 1993 年起,Zuckerman 便深耕偽隨機(jī)性研究,此次獲獎的論文正是其學(xué)術(shù)生涯的里程碑之一。
哥德爾獎由歐洲理論計(jì)算機(jī)科學(xué)協(xié)會 (EATCS) 與 ACM SIGACT 聯(lián)合設(shè)立,獎項(xiàng)以 20 世紀(jì)最偉大的邏輯學(xué)家 Kurt Gödel 命名,以紀(jì)念他在數(shù)學(xué)邏輯領(lǐng)域的革命性貢獻(xiàn)如哥德爾不完備定理及其對「P 與 NP 問題」的早期探索。
自 1993 年首屆頒獎以來,哥德爾獎已成為理論計(jì)算機(jī)科學(xué)領(lǐng)域最具影響力的榮譽(yù)之一,表彰「對領(lǐng)域產(chǎn)生深遠(yuǎn)影響的傑出論文」。此前,華人學(xué)者已多次登頂:滕尚華 (Shang-Hua Teng) 在 2008 年跟 2015 年兩度獲獎,蔡進(jìn)一 (Jin-Yi Cai) 與陳穎(Xi Chen)2021 年因約束滿足問題研究獲獎。此外,包括圖靈獎得主 Shafi Goldwasser 在內(nèi)六位學(xué)者曾兩次獲獎,足見獎項(xiàng)的權(quán)威性。
哥德爾獎的意義,遠(yuǎn)不止於表揚(yáng)個(gè)人成就,每一次頒發(fā)都在為理論計(jì)算機(jī)科學(xué)的未來錨定方向,從偽隨機(jī)性的應(yīng)用如密碼學(xué)、分散式系統(tǒng),再到計(jì)算複雜性的本質(zhì)探索。
這次 Chattopadhyay 與 Zuck「erman 的獲獎,不僅是對他們個(gè)人智慧的肯定,更是對理論計(jì)算機(jī)科學(xué)「從 0 到 1」探索精神的致敬。當(dāng)理論計(jì)算機(jī)科學(xué)從實(shí)驗(yàn)室走向現(xiàn)實(shí)世界,哥德爾獎的光芒將繼續(xù)照亮後來者的探索之路。
新聞來源 (不包括新聞圖片): 鉅亨網(wǎng)