2023圖靈獎(jiǎng)得主揭曉！史上首位計(jì)算機(jī)和數(shù)學(xué)最高獎(jiǎng)“雙料王”誕生

重磅消息！北京時(shí)間4月10日下午5點(diǎn)整，ACM宣布把2023年圖靈獎(jiǎng)?lì)C給Avi Wigderson，以表彰Wigderson對計(jì)算理論和隨機(jī)性做出的奠基性貢獻(xiàn)。

ACM圖靈獎(jiǎng)通常被稱為“計(jì)算機(jī)領(lǐng)域的諾貝爾獎(jiǎng)”，獎(jiǎng)金為100萬美元，通常頒發(fā)給計(jì)算機(jī)科學(xué)各領(lǐng)域的研究領(lǐng)袖。

計(jì)算理論和隨機(jī)性的領(lǐng)袖

Wigderson是普林斯頓高等研究院數(shù)學(xué)學(xué)院的教授，他是計(jì)算復(fù)雜性理論、算法和優(yōu)化、隨機(jī)性和密碼學(xué)、并行和分布式計(jì)算、組合學(xué)和圖論以及理論計(jì)算機(jī)科學(xué)與數(shù)學(xué)等科學(xué)之間的聯(lián)系等領(lǐng)域的領(lǐng)軍人物。^[1]

Wigderson教授，2013年當(dāng)選美國國家科學(xué)院院士，2018年因?qū)Α袄碚撚?jì)算機(jī)科學(xué)和數(shù)學(xué)的貢獻(xiàn)”被授予ACM會士。2021年，Wigderson獲得阿貝爾獎(jiǎng)，“以表彰他們對理論計(jì)算機(jī)科學(xué)和離散數(shù)學(xué)的基礎(chǔ)性貢獻(xiàn)，以及他們將其塑造為現(xiàn)代數(shù)學(xué)的中心領(lǐng)域方面的領(lǐng)導(dǎo)作用”^[2]

這次Wigderson獲得圖靈獎(jiǎng)，也成為了第一個(gè)同時(shí)獲得過圖靈獎(jiǎng)和阿貝爾獎(jiǎng)的人。

什么是計(jì)算理論

計(jì)算理論涉及計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)。它提出的問題包括“這個(gè)問題是否可以通過計(jì)算解決”和“如果這個(gè)問題可以通過計(jì)算解決，需要多少時(shí)間和其他資源？”

計(jì)算理論還探索高效算法的設(shè)計(jì)，雖然并不直接涉及改進(jìn)計(jì)算的實(shí)際應(yīng)用，但其研究成果是計(jì)算機(jī)科學(xué)各領(lǐng)域的基礎(chǔ)，比如密碼學(xué)、計(jì)算生物學(xué)、網(wǎng)絡(luò)設(shè)計(jì)、機(jī)器學(xué)習(xí)和量子計(jì)算等。

什么是計(jì)算的隨機(jī)性

計(jì)算的隨機(jī)性研究是計(jì)算理論的一個(gè)子集，從根本上來說，計(jì)算機(jī)是確定性系統(tǒng)，意味著給定特定的輸入，算法的指令集將準(zhǔn)確預(yù)測計(jì)算的輸出。

然而，現(xiàn)實(shí)世界充斥著難以預(yù)測的隨機(jī)事件，如天氣變化和量子現(xiàn)象。為了提升算法效率，計(jì)算機(jī)科學(xué)家引入了能在計(jì)算過程中進(jìn)行隨機(jī)選擇的概率算法，成功解決了一些難以找到有效確定性解決方案的問題，盡管這些算法可能包含微小的誤差概率。

這引出了是否能完全去除隨機(jī)性、所需隨機(jī)性的質(zhì)量，以及如何理解和利用計(jì)算中的隨機(jī)性與偽隨機(jī)性等基本問題。深入理解這些動(dòng)態(tài)將有助于我們開發(fā)更好的算法，并深化對計(jì)算本質(zhì)的認(rèn)識。

Wigderson的卓越貢獻(xiàn)

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

上世紀(jì)40年代，烏拉姆和馮·諾依曼共同發(fā)明的蒙特卡羅方法，開啟了隨機(jī)算法的先河。

在上世紀(jì)70年代末，計(jì)算機(jī)科學(xué)家們已經(jīng)發(fā)現(xiàn)：隨機(jī)性和計(jì)算難度之間存在顯著聯(lián)系，對于許多難題，采用隨機(jī)性的算法（也稱為概率算法）可以遠(yuǎn)遠(yuǎn)勝過其確定性方案，比如當(dāng)時(shí)的拉斯維加斯算法。

在80年代，BPP復(fù)雜性類的建立，標(biāo)志著對隨機(jī)算法計(jì)算復(fù)雜性系統(tǒng)性研究的開始，BPP類描述了那些可以在多項(xiàng)式時(shí)間內(nèi)解決且具有誤差概率的算法。Wigderson在該領(lǐng)域的三項(xiàng)研究深遠(yuǎn)地影響了計(jì)算機(jī)科學(xué)的各個(gè)學(xué)科：

Hardness vs. Randomness

BPP has subexponential time simulations unlessEXPTIME has publishable

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma

此外，除了隨機(jī)性方面的工作之外，Wigderson也是理論計(jì)算機(jī)科學(xué)其他幾個(gè)領(lǐng)域的知識領(lǐng)袖，包括多證明者交互式證明、密碼學(xué)和電路復(fù)雜性。

圖靈獎(jiǎng)背后的故事

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

Wigderson在采訪中這樣描述父親對他的影響：就是他讓我感染了數(shù)學(xué)這種“病毒”。

本來大學(xué)想主修數(shù)學(xué)專業(yè)的他，卻被父母勸導(dǎo)學(xué)計(jì)算機(jī)，理由是:

計(jì)算機(jī)科學(xué)是一個(gè)年輕的領(lǐng)域，可能更好找工作

果然，是金子到哪里都會發(fā)光。

后來年輕的威格德森于1980年在以色列理工學(xué)院取得學(xué)士學(xué)位，在短短三年內(nèi)，又于1983年在普林斯頓大學(xué)獲得了計(jì)算機(jī)科學(xué)博士學(xué)位。他先后在加利福尼亞大學(xué)伯克利分校、圣何塞IBM研究院、美國國家數(shù)學(xué)科學(xué)研究所和耶路撒冷希伯來大學(xué)擔(dān)任過職位，2003年成為普林斯頓高等研究院的全職人員。

后來又同時(shí)拿到了計(jì)算機(jī)的諾獎(jiǎng)——圖靈獎(jiǎng)以及數(shù)學(xué)的諾獎(jiǎng)——阿貝爾獎(jiǎng)，也成了歷史上目前唯一一個(gè)達(dá)成此成就的人。Wigderson的貢獻(xiàn)過于矚目，以至于有人覺得圖靈獎(jiǎng)早就頒該給他。

除了突破性的技術(shù)貢獻(xiàn)外，Wigderson在為人方面也是好評如潮，他被認(rèn)為是一位受人尊敬的導(dǎo)師和同事，為無數(shù)年輕研究人員提供了建議。

此外，Wigderson雖身為一名以色列人，但他堅(jiān)定地反對以色列對他國領(lǐng)土的侵占，并致力于尋找以色列與巴勒斯坦之間的共同政治解決方案。

他的光輝不僅來源于智慧，還伴隨著奉獻(xiàn)和道義，這激勵(lì)著我們所有人。

參考資料