剛剛，圖靈獎揭曉！史上首位數(shù)學(xué)和計算機(jī)最高獎“雙料王”出現(xiàn)了

豐色 2024-04-10 23:52:57 來源：量子位

白交 豐色 發(fā)自 凹非寺

量子位 | 公眾號 QbitAI

剛剛，“計算機(jī)界最高榮譽(yù)”圖靈獎揭曉——

復(fù)雜性理論先驅(qū)、普林斯頓高等研究院教授艾維·維格森(Avi Wigderson)摘得。

美國計算機(jī)協(xié)會（ACM）表示，表彰他對計算理論的基礎(chǔ)性貢獻(xiàn)，包括重塑人類對計算中隨機(jī)性作用的理解，以及數(shù)十年來在理論計算機(jī)科學(xué)領(lǐng)域的領(lǐng)導(dǎo)地位。

加上2021年獲得的阿貝爾獎，維格森教授現(xiàn)在一舉成為首個同時拿下數(shù)學(xué)和計算機(jī)最高獎的科學(xué)家。

（阿貝爾獎也被譽(yù)為“數(shù)學(xué)界諾貝爾獎”）。

此外，他還是2017年阿里達(dá)摩院剛成立時首批“十大祖師”之一。

業(yè)內(nèi)人士紛紛趕來表示祝賀，a16z的研發(fā)主管表示：除了已有的學(xué)術(shù)成果外，也是因為他幾十年來孜孜不倦的領(lǐng)導(dǎo)力，才帶來理論計算機(jī)科學(xué)界的長青與活力。

比如，沒有他，可能就不會有西蒙斯計算理論研究所。

值得一提的是，他還在5個月前來到清華叉院做客，對當(dāng)下大語言模型的發(fā)展表達(dá)了自己的看法。

復(fù)雜性理論先驅(qū)榮獲圖靈獎

作為一名數(shù)學(xué)家和計算機(jī)科學(xué)家，維格森最重要的貢獻(xiàn)就是增強(qiáng)了人類對計算中隨機(jī)性和偽隨機(jī)性作用的理解。

具體什么意思？

20實際70年代末，計算機(jī)科學(xué)家們已經(jīng)發(fā)現(xiàn)：

隨機(jī)性和計算難度之間存在顯著聯(lián)系。

（這里的計算難度之高指的是那些沒有有效算法，即無法在合理的時間內(nèi)解決的自然問題，它們計算起來比較困難。）

通俗一點解釋就是：

對于許多難題，采用隨機(jī)性的算法（也稱為概率算法）可以遠(yuǎn)遠(yuǎn)勝過其確定性方案。

例如，在一個被稱為“1977證明”的實現(xiàn)中，兩位科學(xué)家就引入了一種隨機(jī)算法，可以比當(dāng)時最好的確定性算法更快地確定一個數(shù)字是否為素數(shù)。

而在20世紀(jì)80年代初，維格森與UC伯克利的科學(xué)家Richard Karp合作，將隨機(jī)性的概念與那些被認(rèn)為計算難度高的問題聯(lián)系起來，也就是沒有已知的確定性算法可以在合理的時間內(nèi)解決這些問題的問題。

盡管不知道如何證明它們很難，維格森和Richard Karp還是發(fā)現(xiàn)了一種針對某個難題的隨機(jī)算法，然后發(fā)現(xiàn)：能夠?qū)⑵淙ルS機(jī)化，從而有效地揭示了它的確定性算法。

大約在同一時間，其他研究人員也發(fā)現(xiàn)密碼學(xué)問題中的計算難度假設(shè)能夠?qū)崿F(xiàn)一般的去隨機(jī)化。

這促使維格森思考隨機(jī)性本身的特質(zhì)。

他和其他人一樣，開始質(zhì)疑隨機(jī)性在高效問題解決中的必要性以及在什么條件下它可以完全被消除。

終于，1994年，他和另一位計算機(jī)科學(xué)家Noam Nisan闡明了兩者之間的聯(lián)系。

他們證明，如果存在任何自然難題，那么每一種有效的隨機(jī)算法都可以被有效的確定性算法所取代。

即我們總是可以消除隨機(jī)性。

更重要的是，他們還發(fā)現(xiàn)確定性算法可能使用“偽隨機(jī)”序列——也就是看似隨機(jī)但實際上并非隨機(jī)的數(shù)據(jù)串。

換句話總結(jié)就是：隨機(jī)性對于高效計算來說并不是必需的。

即使在沒有隨機(jī)性的情況下，我們?nèi)匀豢梢允褂糜行У乃惴▉斫鉀Q問題。

這一系列研究徹底改變了計算機(jī)科學(xué)家對隨機(jī)性的看法，并適用于理論計算機(jī)科學(xué)的許多領(lǐng)域。

今天，ACM就將圖靈獎這一重要榮譽(yù)頒給了維格森，主要嘉獎的就是他在如上領(lǐng)域的貢獻(xiàn)。

在普林斯頓高等研究院的采訪中，維格森解釋自己既是一位數(shù)學(xué)家也是一位計算機(jī)理論科學(xué)家，研究的是計算領(lǐng)域的數(shù)學(xué)基礎(chǔ)。

我的研究領(lǐng)域是數(shù)學(xué)的一個子域，但同時，我所研究的主要概念是計算。

對于理論計算機(jī)科學(xué)，他則認(rèn)為這個學(xué)科擁有一個人對學(xué)術(shù)研究所能期望的所有優(yōu)點，包含了一系列令人驚嘆的深刻且具有重要智力意義的基本問題，而這些問題對人類、科學(xué)、生活和技術(shù)都至關(guān)重要。

（看得出老爺子滿滿的熱愛之情了。）

而對于本次大獎，維格森則表示：

自己很高興看到ACM再次認(rèn)可計算基礎(chǔ)理論，它確實對計算科學(xué)的實踐和技術(shù)發(fā)展做出了巨大貢獻(xiàn)。

大學(xué)被勸學(xué)計算機(jī)“好找工作”

維格森于1956年在以色列出生，是一位護(hù)士和一名電氣工程師的兒子。他的父親喜歡拼圖，并對數(shù)學(xué)的基本概念非常感興趣，然后又經(jīng)常跟孩子們分享他的想法。

維格森這樣描述父親對他的潛移默化的影響：就是他讓我感染了這種病毒。

不過等他要在當(dāng)?shù)睾７ù髮W(xué)上學(xué)時，本想主修數(shù)學(xué)的他，卻被他的父母勸導(dǎo)說：

選擇計算機(jī)吧，計算機(jī)好找工作！

結(jié)果他發(fā)現(xiàn)這個領(lǐng)域有很多數(shù)學(xué)問題沒有解決，于是開始吭哧吭哧解決了起來。

維格森畢業(yè)于以色列理工學(xué)院和美國普林斯頓大學(xué)，1983 年憑借論文《組合復(fù)雜性的研究》獲得博士學(xué)位。

他早期的一項開創(chuàng)性工作，就是證明了一個看似矛盾的問題：

能不能在不展示證明過程的情況下，讓別人相信一個數(shù)學(xué)論斷已經(jīng)被證明了。

是不是想起隱私計算領(lǐng)域姚期智提出的百萬富翁問題內(nèi)味了。

那個問題就是兩個百萬富翁，他們想證明誰更富有，但兩個人都不透露他們擁有多少財富。

而原本的這個問題其實是叫做零知識證明，這個概念最早在1985年由三位科學(xué)家引入。隨后由維格森以及他的合作伙伴Micali和Oded Goldreich進(jìn)一步闡述了這一想法，并發(fā)現(xiàn)了一個意想不到的結(jié)果：如果真正安全加密是可能的，那么 NP 中每個問題的解也都可以用零知識證明來證明。

換言之，零知識證明可以用于秘密地證明任何有關(guān)秘密數(shù)據(jù)的公開結(jié)果。

數(shù)十年來，他始終活躍在學(xué)術(shù)崗位上，并且獲得諸多贊譽(yù)和獎項。1994年，他因在計算復(fù)雜性理論方面的工作獲得1994年的內(nèi)萬林納

博士畢業(yè)后，他在加州大學(xué)伯克利分校擔(dān)任客座助理教授，在IBM擔(dān)任訪問科學(xué)家，并在伯克利的數(shù)學(xué)科學(xué)研究所擔(dān)任研究員。1986年加入希伯來大學(xué)擔(dān)任教員。

1994年，他與Omer Reingold和Salil Vadhan一起因在圖的 zig-zag 乘積方面的工作而獲得了 2009 年哥德爾獎。

1999年，他加入普林斯頓高等研究院并工作至今。2013年當(dāng)選美國國家科學(xué)院院士。

2018年，他因?qū)τ嬎銠C(jī)科學(xué)和數(shù)學(xué)理論的貢獻(xiàn)當(dāng)選ACM Fellow。

第二年，又因為“在隨機(jī)計算、密碼學(xué)、電路復(fù)雜性、證明復(fù)雜性、并行計算以及我們對基本圖特性的理解等領(lǐng)域?qū)τ嬎銠C(jī)科學(xué)基礎(chǔ)做出的根本性和持久性貢獻(xiàn)”，他榮獲高德納獎。

2021年，維格森與László Lovász共同獲得阿貝爾獎。

也正因為這樣根本性且持久性的貢獻(xiàn)，網(wǎng)友們得知他才獲圖靈獎時感到意外而又驚喜，還以為他早就得了。

也有人開始看他曾經(jīng)寫過的書籍了。

或許有眼熟的朋友嗎？

談大語言模型：最重要還是看它不能做什么

而他與姚期智以及中國的緣分還在延續(xù)。

5個月前，他還曾親自來到清華叉院做客，帶來題為“模仿游戲（Imitation Games）”的特邀報告。

由姚期智院士親自主持講座，并與他展開對話。

據(jù)報道，維格森從圖靈測試出發(fā)，敘述了“模仿學(xué)習(xí)”理論的沿革及其在密碼學(xué)、隨機(jī)性、離散數(shù)學(xué)、數(shù)論等領(lǐng)域的現(xiàn)代應(yīng)用。

他基于凱撒密碼、恩尼格瑪密碼機(jī)、選舉等案例，引導(dǎo)思考安全性的定義、隨機(jī)性的應(yīng)用、隱私和效用的平衡等問題。

對于理論計算機(jī)研究將如何應(yīng)對人工智能發(fā)展這一問題，維格森表示，

盡管包括大語言模型在內(nèi)的人工智能有很多驚人表現(xiàn)，但最重要的問題是還有什么是AI不能做的。

對于給現(xiàn)在正置身于科研的同學(xué)們，維格森也給出了自己的建議。

他表示，自己曾為解決一個開放性問題用了40年時間，建議同學(xué)們要選擇自己喜歡的研究領(lǐng)域和話題，并享受在失敗中不斷學(xué)習(xí)的過程，這樣才能在科研道路上走得長遠(yuǎn)。

參考鏈接：
[1]https://www.acm.org/media-center/2024/april/turing-award-2023
[2]https://www.ias.edu/news/avi-wigderson-2023-acm-am-turing-award
[3]https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/
[4]https://www.youtube.com/watch?v=TK_vD-VnsFw
[5]https://x.com/Tim_Roughgarden/status/1778032735849967818
[6]https://x.com/letonyo/status/1777987622301769771