新智元報道??

來源：nature

編輯：小勻

【新智元導(dǎo)讀】昨日消息，數(shù)學(xué)界三大獎項之一「阿貝爾獎」揭曉。挪威科學(xué)和文學(xué)院將2021年阿貝爾獎授予匈牙利厄特沃什·羅蘭大學(xué)教授László Lovász和美國普林斯頓高等研究院教授Avi Wigderson，他們是「聯(lián)系數(shù)學(xué)與計算機科學(xué)的先驅(qū)者」。

剛剛，挪威科學(xué)與文學(xué)院公布了年度阿貝爾獎的獲得者是阿維·威格森（Avi Wigderson）和洛瓦茲·拉茲洛?(Lovász László），以表彰他們在「理論計算機科學(xué)和離散數(shù)學(xué)方面做出的杰出貢獻，以及使其在現(xiàn)代數(shù)學(xué)中心領(lǐng)域中發(fā)揮主導(dǎo)作用�！�

阿貝爾獎是數(shù)學(xué)界的最高榮譽之一，被稱為數(shù)學(xué)界的諾貝爾獎，與菲爾茲獎齊名，前者主要吸引年輕人從事數(shù)學(xué)研究，一起擴大數(shù)學(xué)的影響是阿貝爾獎設(shè)立的主要目的。

曾獲過這個獎項的數(shù)學(xué)家包括證明費馬大定理的懷爾斯（Andreww J. Wiles）、電影《美麗心靈》原型約翰·納什（John Nash），以及目前唯一一位女性獲得者凱倫·烏倫貝克（Karen Keskulla Uhlenbeck）等。

曾幾何時，計算機科學(xué)和純數(shù)學(xué)幾乎是完全獨立的學(xué)科。如今，它們之間的距離是如此之近，以至于很難找到它們之間的界線。

Avi在計算機方面有卓越成果，而Lovász則在數(shù)學(xué)的天才，他們的研究相互交錯，對理解計算中的隨機性和探索高效計算的邊界做出了巨大貢獻。

他們在2012年的阿貝爾頒獎禮上聊天，10年后，他們將分享這一大獎

Avi Wigderson：「去隨機化」的以色列計算機學(xué)家

威格森1956年出生于以色列海法。

在他十幾歲的時候，計算機科學(xué)家剛剛開始勾畫一個基本的理論框架——復(fù)雜性理論，涉及根據(jù)算法解決計算問題的難易程度對其進行分類。而衡量難度的主要標準是計算步驟的數(shù)量，最基本的區(qū)別是「易」與「難」。

一個簡單的計算問題的例子是將兩個數(shù)相乘。無論數(shù)字變得多么大，計算機都能很快找到它們的乘積。這個問題屬于復(fù)雜度類「P」，它包含了所有容易解決的計算問題。

相比之下，有些計算問題則看起來很難，比如，尋找一個數(shù)的質(zhì)因數(shù)（prime factor，能整除給定正整數(shù)的質(zhì)數(shù)）。

目前，已知算法還沒有能快速做到這一點的。但反過來就容易多了，如果你知道了某個數(shù)的質(zhì)因數(shù)，只要把它們乘在一起，你就知道它們是正確的。這個問題屬于「NP」，它包含的計算問題可能很難解決，但其答案很容易驗證。

這也被稱為「去隨機化」，從這里開始，人們開始認真思考隨機性也沒那么重要。

20世紀70年代初，計算機科學(xué)家提出了復(fù)雜性理論的指導(dǎo)性猜想，問P中的問題列表是否與NP中的問題完全對應(yīng)，也就是之后爭論不休的：復(fù)雜度類P和NP是否是等價的（P=NP?）

這也是讓威格森初露鋒芒的地方。

1977年，當威格森進入以色列理工學(xué)院時，這個問題還很「時髦」。

在接下來的幾十年里，他幫助闡述了將復(fù)雜性類別一一歸位。

后來，威格森發(fā)表了兩篇論文，在人們普遍認可的計算假設(shè)下，每個概率多項式時間算法都可以完全去隨機化(derandomized)。換句話說，多項式時間計算不需要隨機性，總是有可能將快速隨機算法轉(zhuǎn)換為快速確定性算法。

結(jié)果確定了稱為BPP的復(fù)雜度類與P完全相同，也就是P = BPP，將數(shù)十年來對隨機算法的研究巧妙地結(jié)合到了復(fù)雜性理論的主體中，并改變了計算機科學(xué)家看待隨機算法的方式。

他還在其職業(yè)生涯早期對互聯(lián)網(wǎng)密碼學(xué)做出了貢獻，包括現(xiàn)在用于加密貨幣技術(shù)的零知識證明。

當然，威格森一直活躍在學(xué)術(shù)崗位。

1983年，威格森在普林斯頓大學(xué)獲得博士學(xué)位。隨后，他在加州大學(xué)伯克利分校擔任客座助理教授，在IBM擔任訪問科學(xué)家，并在伯克利的數(shù)學(xué)科學(xué)研究所(MSRI)擔任研究員，1986年加入希伯來大學(xué)(Hebrew University)擔任教員。自1999年以來，Wigderson一直是高等研究院數(shù)學(xué)學(xué)院的教授。Wigderson還在2009年獲得哥德爾獎(Godel Prize)，獲獎原因是他與Omer Reingold和Salil Vadhan合作的工作，并在1994年獲得了內(nèi)萬林納獎(Nevanlinna Prize)。

2018，威格森因?qū)τ嬎銠C科學(xué)和數(shù)學(xué)理論的貢獻（Institute for Advanced Study）當選ACM Fellow，他還是首批坐鎮(zhèn)阿里達摩院的十位「達摩祖師」之一。

Lovász László：數(shù)學(xué)明星、LLL算法創(chuàng)始人

洛瓦茲1948年出生在布達佩斯，從小就算是數(shù)學(xué)界的明星。

十幾歲時，他就三塊金牌加深：1964年、1965年及1966年國際數(shù)學(xué)奧林匹克競賽金牌。22歲，洛瓦茲獲得于布達佩斯羅蘭大學(xué)計算機科學(xué)博士學(xué)位。

在他年輕的時候，洛瓦茲遇到了他的伯樂：匈牙利數(shù)學(xué)家Paul Erd?s，后者幫助他進入了圖論領(lǐng)域。

在當時，圖論是一個數(shù)學(xué)上的「寶藏」，以提出一些有趣的問題而聞名，比如四色猜想（現(xiàn)在是一個已被證明的定理），在任何地圖上，是否總能用四種顏色給國家上色，并且沒有兩個相鄰的國家有相同的顏色。

洛瓦茲研究的主要影響之一是確立了離散數(shù)學(xué)能夠解決計算機科學(xué)基本理論問題的方法。他說，「能夠親身經(jīng)歷一段數(shù)學(xué)發(fā)展與應(yīng)用領(lǐng)域完全契合的時期，感到非常幸運�！�

洛瓦茲的許多工作都集中在解決各種問題的算法的開發(fā)上。他最有影響的結(jié)果之一是LLL算法，該算法以其洛瓦茲以及Arjen和Hendrik Lenstra兄弟命名。該算法適用于被稱為格的幾何對象，這些幾何對象是空間中的點集，其坐標通常具有整數(shù)值。

LLL算法解決了有關(guān)其屬性的一個基本問題：晶格中的哪個點最接近原點？這是一個通常很難解決的簡單問題，尤其是在高維空間中以及晶格中的點何時形成扭曲的形狀。

目前，唯一已知能夠承受量子計算機攻擊的加密系統(tǒng)正是基于 LLL 算法。

洛瓦茲榮獲過多個獎項，包括 1999 年沃爾夫獎、1999 年高德納獎、2001 年哥德爾獎和2010年京都獎。2007年至2010年，洛瓦茲擔任國際數(shù)學(xué)聯(lián)盟主席。他還于2014年至2020年擔任匈牙利科學(xué)院院長，在這些年里，他為阻止匈牙利政府接管該學(xué)院的研究機構(gòu)而做出了大膽的努力，他和其他許多人認為，此舉將降低研究人員的獨立性。

遺憾的是，他們最終沒有成功。

自從2003年授予阿貝爾獎以來，洛瓦茲是第三位在匈牙利出生的人，而威格森則是第二位以色列人，獲獎?wù)邔�獲得獎金約750萬挪威克朗（約合人民幣575萬元）。

參考鏈接：

https://en.wikipedia.org/wiki/Avi_Wigderson

https://www.nature.com/articles/d41586-019-00586-z

https://www.quantamagazine.org/avi-wigderson-and-laszlo-lovasz-win-abel-prize-20210317/

推薦你看：

AI模型加速進入萬億級時代，中國AI算力獨占全球三成

慘烈！特斯拉再次撞上白色卡車，兩名乘客急送ICU

    本文首發(fā)于微信公眾號：新智元。文章內(nèi)容屬作者個人觀點，不代表和訊網(wǎng)立場。投資者據(jù)此操作，風(fēng)險請自擔。