2023圖靈獎(jiǎng)出爐！計(jì)算機(jī)的“隨機(jī)性”為何如此重要？

昨晚，美國(guó)計(jì)算機(jī)協(xié)會(huì)（ACM）宣布將 2023 年 ACM A.M. 圖靈獎(jiǎng)授予數(shù)學(xué)家和頂級(jí)理論計(jì)算機(jī)科學(xué)家 Avi Wigderson，以表彰他對(duì)計(jì)算理論的奠基性貢獻(xiàn)，包括重塑我們對(duì)隨機(jī)性在計(jì)算中的作用的理解，以及他數(shù)十年來對(duì)理論計(jì)算機(jī)科學(xué)領(lǐng)域的引領(lǐng)。

ACM A.M. 圖靈獎(jiǎng)由 ACM 于 1966 年設(shè)立，專門獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人。圖靈獎(jiǎng)名稱取自計(jì)算機(jī)科學(xué)先驅(qū)、英國(guó)科學(xué)家 Alan M. Turing，這個(gè)獎(jiǎng)設(shè)立目的之一正是為了紀(jì)念這位偉大的科學(xué)家。

圖靈獎(jiǎng)對(duì)獲獎(jiǎng)?wù)咭髽O高，評(píng)獎(jiǎng)程序極嚴(yán)，一般每年只獎(jiǎng)勵(lì)一名計(jì)算機(jī)科學(xué)家，只有極少數(shù)年度有兩名在同一方向上做出貢獻(xiàn)的科學(xué)家同時(shí)獲獎(jiǎng)。因此，圖靈獎(jiǎng)也是計(jì)算機(jī)界最負(fù)盛名、最崇高的一個(gè)獎(jiǎng)項(xiàng)，有 “計(jì)算機(jī)界的諾貝爾獎(jiǎng)” 之稱。

什么是理論計(jì)算機(jī)科學(xué)？

理論計(jì)算機(jī)科學(xué)關(guān)注該領(lǐng)域的數(shù)學(xué)基礎(chǔ)。它提出的問題包括：“這個(gè)問題是否可以通過計(jì)算解決？”或“如果這個(gè)問題可以通過計(jì)算解決，那么需要多少時(shí)間和其他資源？” 理論計(jì)算機(jī)科學(xué)還探索高效算法的設(shè)計(jì)。

與我們生活息息相關(guān)的每一項(xiàng)計(jì)算技術(shù)都是通過算法實(shí)現(xiàn)的。了解強(qiáng)大高效算法的原理，不僅能加深我們對(duì)計(jì)算機(jī)科學(xué)的理解，還能加深我們對(duì)自然規(guī)律的理解。從密碼學(xué)和計(jì)算生物學(xué)到網(wǎng)絡(luò)設(shè)計(jì)、機(jī)器學(xué)習(xí)和量子計(jì)算，理論計(jì)算機(jī)科學(xué)的研究突破幾乎推動(dòng)了該學(xué)科各個(gè)領(lǐng)域的進(jìn)步。

為什么隨機(jī)性很重要？

從根本上說，計(jì)算機(jī)是確定性系統(tǒng)；應(yīng)用于任何給定輸入的算法指令集唯一地決定了其計(jì)算，尤其是其輸出。換句話說，確定性算法遵循的是一種可預(yù)測(cè)的模式。相比之下，隨機(jī)性則缺乏明確的模式，或者說事件或結(jié)果缺乏可預(yù)測(cè)性。由于我們生活的世界中充滿了天氣系統(tǒng)、生物和量子現(xiàn)象等隨機(jī)事件，計(jì)算機(jī)科學(xué)家豐富了算法，允許它們?cè)谟?jì)算過程中做出隨機(jī)選擇，借此提高算法的效率。事實(shí)上，許多沒有已知高效確定性算法的問題，已經(jīng)通過概率算法得到了高效解決，盡管存在一些小概率錯(cuò)誤（可以有效減少）。

但是，隨機(jī)性是必不可少的，還是可以去除？概率算法成功所需的隨機(jī)性質(zhì)量又如何？ 這些問題以及其他許多基本問題是理解計(jì)算中隨機(jī)性和偽隨機(jī)性的關(guān)鍵。加深對(duì)計(jì)算中隨機(jī)性動(dòng)態(tài)的理解，可以幫助我們開發(fā)出更好的算法，并加深我們對(duì)計(jì)算本身性質(zhì)的理解。

Wigderson 的貢獻(xiàn)

Wigderson 在計(jì)算復(fù)雜性理論、算法與優(yōu)化、隨機(jī)性與密碼學(xué)、并行與分布式計(jì)算、組合學(xué)、圖論以及理論計(jì)算機(jī)科學(xué)與數(shù)學(xué)和科學(xué)之間的聯(lián)系等領(lǐng)域，一直處于引領(lǐng)地位。

四十年來，Wigderson 一直是計(jì)算機(jī)科學(xué)理論研究領(lǐng)域的引領(lǐng)人物，他在理解隨機(jī)性和偽隨機(jī)性在計(jì)算中的作用方面做出了奠基性的貢獻(xiàn)。

計(jì)算機(jī)科學(xué)家發(fā)現(xiàn)了隨機(jī)性與計(jì)算難度之間的顯著聯(lián)系（即確定沒有高效算法的自然問題）。Wigderson 與同事合作，撰寫了一系列極具影響力的關(guān)于用隨機(jī)性換取難度的著作。他們證明，在標(biāo)準(zhǔn)的、被廣泛相信的計(jì)算假設(shè)下，每一種概率多項(xiàng)式時(shí)間算法都可以有效地去隨機(jī)化（即完全確定）。

換句話說，隨機(jī)性并不是高效計(jì)算的必要條件。這一系列著作徹底改變了我們對(duì)隨機(jī)性在計(jì)算中的作用的理解，也改變了我們對(duì)隨機(jī)性的思考方式。這些影響深遠(yuǎn)的論文包括以下三篇：

1）“Hardness vs. Randomness”（與 Noam Nisan 合著）。 除其他發(fā)現(xiàn)外，這篇論文還介紹了一種新型偽隨機(jī)發(fā)生器，并證明了在比以前已知的假設(shè)更弱的條件下，隨機(jī)算法的高效確定性模擬是可能的。

論文鏈接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

2）“BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs”（與 László Babai、Lance Fortnow 和 Noam Nisan 合著） 這篇論文利用“hardness amplification”證明，在較弱的假設(shè)條件下，有界錯(cuò)誤概率多項(xiàng)式時(shí)間（BPP）可以在亞指數(shù)時(shí)間內(nèi)模擬無限多的輸入長(zhǎng)度。

論文鏈接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

3）“P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma”（與 Russell Impagliazzo 合著） 這篇論文介紹了一種更強(qiáng)的偽隨機(jī)發(fā)生器，它在硬度與隨機(jī)性之間實(shí)現(xiàn)了基本最優(yōu)的權(quán)衡。

論文鏈接：https://dl.acm.org/doi/pdf/10.1145/258533.258590

重要的是，這三篇論文的影響遠(yuǎn)遠(yuǎn)超出了隨機(jī)性和反隨機(jī)化領(lǐng)域。這些論文中的觀點(diǎn)后來被應(yīng)用于理論計(jì)算機(jī)科學(xué)的許多領(lǐng)域，并推動(dòng)了該領(lǐng)域多位領(lǐng)軍人物發(fā)表具有影響力的論文。 后來，Wigderson 與 Omer Reingold、Salil Vadhan 和 Michael Capalbo 合作，仍然在計(jì)算隨機(jī)性的廣泛領(lǐng)域開展工作，在另一篇論文中首次提出了擴(kuò)展圖的高效組合構(gòu)造，擴(kuò)展圖是一種稀疏圖，具有很強(qiáng)的連通性。它們?cè)跀?shù)學(xué)和理論計(jì)算機(jī)科學(xué)領(lǐng)域都有許多重要應(yīng)用。

論文鏈接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf

除了在隨機(jī)性方面的研究之外，Wigderson 還是多驗(yàn)證器交互式證明、密碼學(xué)和電路復(fù)雜性等理論計(jì)算機(jī)科學(xué)內(nèi)多幾個(gè)領(lǐng)域的領(lǐng)袖。

受人尊敬的導(dǎo)師

除了開創(chuàng)性的技術(shù)貢獻(xiàn)，Wigderson 還是公認(rèn)的受人尊敬的導(dǎo)師和同事，為無數(shù)年輕研究人員提供建議。廣博的知識(shí)和優(yōu)秀的技術(shù)能力，加上友善、熱情和慷慨，讓他吸引了許多最優(yōu)秀的年輕人投身于理論計(jì)算機(jī)科學(xué)領(lǐng)域。

“必須指出的是，Avi Wigderson 還獲得了阿貝爾獎(jiǎng)（Abel Prize），該獎(jiǎng)項(xiàng)被認(rèn)為是數(shù)學(xué)領(lǐng)域終身成就最重要的榮譽(yù)，” ACM 主席 Yannis Ioannidis 說道。 “Avi Wigderson 在隨機(jī)性和其他課題方面的工作在過去三十年里為理論計(jì)算機(jī)科學(xué)制定了方向，” 谷歌高級(jí)副總裁 Jeff Dean 解釋說，“從計(jì)算機(jī)科學(xué)誕生之初，研究人員就認(rèn)識(shí)到，隨機(jī)性是為各種應(yīng)用設(shè)計(jì)更快算法的一種方法。為更好地理解隨機(jī)性所做的努力將繼續(xù)為我們的領(lǐng)域帶來重要益處，Wigderson 在這一領(lǐng)域開辟了新天地?！?/p>

Wigderson 的履歷

自 1999 年以來，Wigderson 一直擔(dān)任普林斯頓高等研究院數(shù)學(xué)學(xué)院赫伯特-H-馬斯教授。此前，他曾擔(dān)任耶路撒冷希伯來大學(xué)教授，并在普林斯頓大學(xué)、加州大學(xué)伯克利分校、IBM 等機(jī)構(gòu)擔(dān)任客座教授。

Wigderson 畢業(yè)于以色列理工學(xué)院，并獲得普林斯頓大學(xué)計(jì)算機(jī)科學(xué)碩士、MSE 和博士學(xué)位。他獲得的榮譽(yù)包括阿貝爾獎(jiǎng)、IMU 算盤獎(jiǎng)、唐納德-E-克努特獎(jiǎng)、Edsger W. Dijkstra 分布式計(jì)算獎(jiǎng)和哥德爾獎(jiǎng)。他是 ACM Fellow、美國(guó)國(guó)家科學(xué)院和美國(guó)藝術(shù)與科學(xué)院院士。

參考鏈接：https://awards.acm.org/about/2023-turing