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

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

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

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

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

他們?cè)?012年的阿貝爾頒獎(jiǎng)禮上聊天，10年后，他們將分享這一大獎(jiǎng)

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

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

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

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

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

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

這也被稱為「去隨機(jī)化」，從這里開(kāi)始，人們開(kāi)始認(rèn)真思考隨機(jī)性也沒(méi)那么重要。

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

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

1977年，當(dāng)威格森進(jìn)入以色列理工學(xué)院時(shí)，這個(gè)問(wèn)題還很「時(shí)髦」。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

遺憾的是，他們最終沒(méi)有成功。

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