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

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

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

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

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

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

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

比如，沒(méi)有他，可能就不會(huì)有西蒙斯計(jì)算理論研究所。

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

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

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

具體什么意思？

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

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

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

通俗一點(diǎn)解釋就是：

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

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

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

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

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

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

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

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

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

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

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

換句話(huà)總結(jié)就是：隨機(jī)性對(duì)于高效計(jì)算來(lái)說(shuō)并不是必需的。

即使在沒(méi)有隨機(jī)性的情況下，我們?nèi)匀豢梢允褂糜行У乃惴▉?lái)解決問(wèn)題。

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

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

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

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

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

（看得出老爺子滿(mǎn)滿(mǎn)的熱愛(ài)之情了。）

而對(duì)于本次大獎(jiǎng)，維格森則表示：

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

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

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

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

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

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

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

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

他早期的一項(xiàng)開(kāi)創(chuàng)性工作，就是證明了一個(gè)看似矛盾的問(wèn)題：

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

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

那個(gè)問(wèn)題就是兩個(gè)百萬(wàn)富翁，他們想證明誰(shuí)更富有，但兩個(gè)人都不透露他們擁有多少財(cái)富。

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

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

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

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

1994年，他與Omer Reingold和Salil Vadhan一起因在圖的 zig-zag 乘積方面的工作而獲得了 2009 年哥德?tīng)柂?jiǎng)。

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

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

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

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

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

也有人開(kāi)始看他曾經(jīng)寫(xiě)過(guò)的書(shū)籍了。

或許有眼熟的朋友嗎？

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

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

5個(gè)月前，他還曾親自來(lái)到清華叉院做客，帶來(lái)題為“模仿游戲（Imitation Games）”的特邀報(bào)告。

由姚期智院士親自主持講座，并與他展開(kāi)對(duì)話(huà)。

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

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

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

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

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

他表示，自己曾為解決一個(gè)開(kāi)放性問(wèn)題用了40年時(shí)間，建議同學(xué)們要選擇自己喜歡的研究領(lǐng)域和話(huà)題，并享受在失敗中不斷學(xué)習(xí)的過(guò)程，這樣才能在科研道路上走得長(zhǎng)遠(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