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

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

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

量子位 | 公眾號 QbitAI

剛剛，“計算機界最高榮譽”圖靈獎揭曉——

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

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

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

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

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

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

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

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

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

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

具體什么意思？

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

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

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

通俗一點解釋就是：

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

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

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

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

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

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

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

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

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

即我們總是可以消除隨機性。

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

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

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

這一系列研究徹底改變了計算機科學家對隨機性的看法，并適用于理論計算機科學的許多領域。

今天，ACM就將圖靈獎這一重要榮譽頒給了維格森，主要嘉獎的就是他在如上領域的貢獻。

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

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

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

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

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

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

大學被勸學計算機“好找工作”

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

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

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

選擇計算機吧，計算機好找工作！

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

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

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

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

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

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

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

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

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

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

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

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

2018年，他因?qū)τ嬎銠C科學和數(shù)學理論的貢獻當選ACM Fellow。

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

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

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

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

或許有眼熟的朋友嗎？

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

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

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

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

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

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

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

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

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

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

參考鏈接：
[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