白交 豐色 發自 凹非寺
量子位 | 公衆号 QbitAI
剛剛，“計算機界最高榮譽”圖靈獎揭曉——
複雜性理論先驅、普林斯頓高等研究院教授艾維·維格森(Avi Wigderson)摘得。
美國計算機協會（ACM）表示，表彰他對計算理論的基礎性貢獻，包括重塑人類對計算中随機性作用的了解，以及數十年來在理論計算機科學領域的上司地位。
加上2021年獲得的阿貝爾獎，維格森教授現在一舉成為首個同時拿下數學和計算機最高獎的科學家。
（阿貝爾獎也被譽為“數學界諾貝爾獎”）。
此外，他還是2017年阿裡達摩院剛成立時首批“十大祖師”之一。
業内人士紛紛趕來表示祝賀，a16z的研發主管表示：除了已有的學術成果外，也是因為他幾十年來孜孜不倦的上司力，才帶來理論計算機科學界的長青與活力。
比如，沒有他，可能就不會有西蒙斯計算理論研究所。
值得一提的是，他還在5個月前來到清華叉院做客，對當下大語言模型的發展表達了自己的看法。
複雜性理論先驅榮獲圖靈獎
作為一名數學家和計算機科學家，維格森最重要的貢獻就是增強了人類對計算中随機性和僞随機性作用的了解。
具體什麼意思？
20實際70年代末，計算機科學家們已經發現：
随機性和計算難度之間存在顯著聯系。
（這裡的計算難度之高指的是那些沒有有效算法，即無法在合理的時間内解決的自然問題，它們計算起來比較困難。）
通俗一點解釋就是：
對于許多難題，采用随機性的算法（也稱為機率算法）可以遠遠勝過其确定性方案。
例如，在一個被稱為“1977證明”的實作中，兩位科學家就引入了一種随機算法，可以比當時最好的确定性算法更快地确定一個數字是否為素數。
而在20世紀80年代初，維格森與UC伯克利的科學家Richard Karp合作，将随機性的概念與那些被認為計算難度高的問題聯系起來，也就是沒有已知的确定性算法可以在合理的時間内解決這些問題的問題。
盡管不知道如何證明它們很難，維格森和Richard Karp還是發現了一種針對某個難題的随機算法，然後發現：能夠将其去随機化，進而有效地揭示了它的确定性算法。
大約在同一時間，其他研究人員也發現密碼學問題中的計算難度假設能夠實作一般的去随機化。
這促使維格森思考随機性本身的特質。
他和其他人一樣，開始質疑随機性在高效問題解決中的必要性以及在什麼條件下它可以完全被消除。
終于，1994年，他和另一位計算機科學家Noam Nisan闡明了兩者之間的聯系。
他們證明，如果存在任何自然難題，那麼每一種有效的随機算法都可以被有效的确定性算法所取代。
即我們總是可以消除随機性。
更重要的是，他們還發現确定性算法可能使用“僞随機”序列——也就是看似随機但實際上并非随機的資料串。
換句話總結就是：随機性對于高效計算來說并不是必需的。
即使在沒有随機性的情況下，我們仍然可以使用有效的算法來解決問題。
這一系列研究徹底改變了計算機科學家對随機性的看法，并适用于理論計算機科學的許多領域。
今天，ACM就将圖靈獎這一重要榮譽頒給了維格森，主要嘉獎的就是他在如上領域的貢獻。
在普林斯頓高等研究院的采訪中，維格森解釋自己既是一位數學家也是一位計算機理論科學家，研究的是計算領域的數學基礎。
我的研究領域是數學的一個子域，但同時，我所研究的主要概念是計算。
對于理論計算機科學，他則認為這個學科擁有一個人對學術研究所能期望的所有優點，包含了一系列令人驚歎的深刻且具有重要智力意義的基本問題，而這些問題對人類、科學、生活和技術都至關重要。
（看得出老爺子滿滿的熱愛之情了。）
而對于本次大獎，維格森則表示：
自己很高興看到ACM再次認可計算基礎理論，它确實對計算科學的實踐和技術發展做出了巨大貢獻。
大學被勸學計算機“好找工作”
維格森于1956年在以色列出生，是一位護士和一名電氣工程師的兒子。他的父親喜歡拼圖，并對數學的基本概念非常感興趣，然後又經常跟孩子們分享他的想法。
維格森這樣描述父親對他的潛移默化的影響：就是他讓我感染了這種病毒。
不過等他要在當地海法大學上學時，本想主修數學的他，卻被他的父母勸導說：
選擇計算機吧，計算機好找工作！
結果他發現這個領域有很多數學問題沒有解決，于是開始吭哧吭哧解決了起來。
維格森畢業于以色列理工學院和美國普林斯頓大學，1983 年憑借論文《組合複雜性的研究》獲得博士學位。
他早期的一項開創性工作，就是證明了一個看似沖突的問題：
能不能在不展示證明過程的情況下，讓别人相信一個數學論斷已經被證明了。
是不是想起隐私計算領域姚期智提出的百萬富翁問題内味了。
那個問題就是兩個百萬富翁，他們想證明誰更富有，但兩個人都不透露他們擁有多少财富。
而原本的這個問題其實是叫做零知識證明，這個概念最早在1985年由三位科學家引入。随後由維格森以及他的合作夥伴Micali和Oded Goldreich進一步闡述了這一想法，并發現了一個意想不到的結果：如果真正安全加密是可能的，那麼 NP 中每個問題的解也都可以用零知識證明來證明。
換言之，零知識證明可以用于秘密地證明任何有關秘密資料的公開結果。
數十年來，他始終活躍在學術崗位上，并且獲得諸多贊譽和獎項。1994年，他因在計算複雜性理論方面的工作獲得1994年的内萬林納
博士畢業後，他在加州大學伯克利分校擔任客座助理教授，在IBM擔任通路科學家，并在伯克利的數學科學研究所擔任研究員。1986年加入希伯來大學擔任教員。
1994年，他與Omer Reingold和Salil Vadhan一起因在圖的 zig-zag 乘積方面的工作而獲得了 2009 年哥德爾獎。
1999年，他加入普林斯頓高等研究院并工作至今。2013年當選美國國家科學院院士。
2018年，他因對計算機科學和數學理論的貢獻當選ACM Fellow。
第二年，又因為“在随機計算、密碼學、電路複雜性、證明複雜性、并行計算以及我們對基本圖特性的了解等領域對計算機科學基礎做出的根本性和持久性貢獻”，他榮獲高德納獎。
2021年，維格森與László Lovász共同獲得阿貝爾獎。
也正因為這樣根本性且持久性的貢獻，網友們得知他才獲圖靈獎時感到意外而又驚喜，還以為他早就得了。
也有人開始看他曾經寫過的書籍了。
或許有眼熟的朋友嗎？
談大語言模型：最重要還是看它不能做什麼
而他與姚期智以及中國的緣分還在延續。
5個月前，他還曾親自來到清華叉院做客，帶來題為“模仿遊戲（Imitation Games）”的特邀報告。
由姚期智院士親自主持講座，并與他展開對話。
據報道，維格森從圖靈測試出發，叙述了“模仿學習”理論的沿革及其在密碼學、随機性、離散數學、數論等領域的現代應用。
他基于凱撒密碼、恩尼格瑪密碼機、選舉等案例，引導思考安全性的定義、随機性的應用、隐私和效用的平衡等問題。
對于理論計算機研究将如何應對人工智能發展這一問題，維格森表示，
盡管包括大語言模型在内的人工智能有很多驚人表現，但最重要的問題是還有什麼是AI不能做的。
對于給現在正置身于科研的同學們，維格森也給出了自己的建議。
他表示，自己曾為解決一個開放性問題用了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
— 完 —
量子位 QbitAI · 頭條号簽約
關注我們，第一時間獲知前沿科技動态