新智元報道??
來源：nature
編輯：小勻
【新智元導讀】昨日消息，數學界三大獎項之一「阿貝爾獎」揭曉。挪威科學和文學院將2021年阿貝爾獎授予匈牙利厄特沃什·羅蘭大學教授László Lovász和美國普林斯頓高等研究院教授Avi Wigderson，他們是「聯系數學與計算機科學的先驅者」。
剛剛，挪威科學與文學院公布了年度阿貝爾獎的獲得者是阿維·威格森（Avi Wigderson）和洛瓦茲·拉茲洛?(Lovász László），以表彰他們在「理論計算機科學和離散數學方面做出的杰出貢獻，以及使其在現代數學中心領域中發揮主導作用。」
阿貝爾獎是數學界的最高榮譽之一，被稱為數學界的諾貝爾獎，與菲爾茲獎齊名，前者主要吸引年輕人從事數學研究，一起擴大數學的影響是阿貝爾獎設立的主要目的。
曾獲過這個獎項的數學家包括證明費馬大定理的懷爾斯（Andreww J. Wiles）、電影《美麗心靈》原型約翰·納什（John Nash），以及目前唯一一位女性獲得者凱倫·烏倫貝克（Karen Keskulla Uhlenbeck）等。
曾幾何時，計算機科學和純數學幾乎是完全獨立的學科。如今，它們之間的距離是如此之近，以至于很難找到它們之間的界線。
Avi在計算機方面有卓越成果，而Lovász則在數學的天才，他們的研究相互交錯，對理解計算中的隨機性和探索高效計算的邊界做出了巨大貢獻。
他們在2012年的阿貝爾頒獎禮上聊天，10年后，他們將分享這一大獎
Avi Wigderson：「去隨機化」的以色列計算機學家
威格森1956年出生于以色列海法。
在他十幾歲的時候，計算機科學家剛剛開始勾畫一個基本的理論框架——復雜性理論，涉及根據算法解決計算問題的難易程度對其進行分類。而衡量難度的主要標準是計算步驟的數量，最基本的區別是「易」與「難」。
一個簡單的計算問題的例子是將兩個數相乘。無論數字變得多么大，計算機都能很快找到它們的乘積。這個問題屬于復雜度類「P」，它包含了所有容易解決的計算問題。
相比之下，有些計算問題則看起來很難，比如，尋找一個數的質因數（prime factor，能整除給定正整數的質數）。
目前，已知算法還沒有能快速做到這一點的。但反過來就容易多了，如果你知道了某個數的質因數，只要把它們乘在一起，你就知道它們是正確的。這個問題屬于「NP」，它包含的計算問題可能很難解決，但其答案很容易驗證。
這也被稱為「去隨機化」，從這里開始，人們開始認真思考隨機性也沒那么重要。
20世紀70年代初，計算機科學家提出了復雜性理論的指導性猜想，問P中的問題列表是否與NP中的問題完全對應，也就是之后爭論不休的：復雜度類P和NP是否是等價的（P=NP?）
這也是讓威格森初露鋒芒的地方。
1977年，當威格森進入以色列理工學院時，這個問題還很「時髦」。
在接下來的幾十年里，他幫助闡述了將復雜性類別一一歸位。
后來，威格森發表了兩篇論文，在人們普遍認可的計算假設下，每個概率多項式時間算法都可以完全去隨機化(derandomized)。換句話說，多項式時間計算不需要隨機性，總是有可能將快速隨機算法轉換為快速確定性算法。
結果確定了稱為BPP的復雜度類與P完全相同，也就是P = BPP，將數十年來對隨機算法的研究巧妙地結合到了復雜性理論的主體中，并改變了計算機科學家看待隨機算法的方式。
他還在其職業生涯早期對互聯網密碼學做出了貢獻，包括現在用于加密貨幣技術的零知識證明。
當然，威格森一直活躍在學術崗位。
1983年，威格森在普林斯頓大學獲得博士學位。隨后，他在加州大學伯克利分校擔任客座助理教授，在IBM擔任訪問科學家，并在伯克利的數學科學研究所(MSRI)擔任研究員，1986年加入希伯來大學(Hebrew University)擔任教員。自1999年以來，Wigderson一直是高等研究院數學學院的教授。Wigderson還在2009年獲得哥德爾獎(Godel Prize)，獲獎原因是他與Omer Reingold和Salil Vadhan合作的工作，并在1994年獲得了內萬林納獎(Nevanlinna Prize)。
2018，威格森因對計算機科學和數學理論的貢獻（Institute for Advanced Study）當選ACM Fellow，他還是首批坐鎮阿里達摩院的十位「達摩祖師」之一。
Lovász László：數學明星、LLL算法創始人
洛瓦茲1948年出生在布達佩斯，從小就算是數學界的明星。
十幾歲時，他就三塊金牌加深：1964年、1965年及1966年國際數學奧林匹克競賽金牌。22歲，洛瓦茲獲得于布達佩斯羅蘭大學計算機科學博士學位。
在他年輕的時候，洛瓦茲遇到了他的伯樂：匈牙利數學家Paul Erd?s，后者幫助他進入了圖論領域。
在當時，圖論是一個數學上的「寶藏」，以提出一些有趣的問題而聞名，比如四色猜想（現在是一個已被證明的定理），在任何地圖上，是否總能用四種顏色給國家上色，并且沒有兩個相鄰的國家有相同的顏色。
洛瓦茲研究的主要影響之一是確立了離散數學能夠解決計算機科學基本理論問題的方法。他說，「能夠親身經歷一段數學發展與應用領域完全契合的時期，感到非常幸運。」
洛瓦茲的許多工作都集中在解決各種問題的算法的開發上。他最有影響的結果之一是LLL算法，該算法以其洛瓦茲以及Arjen和Hendrik Lenstra兄弟命名。該算法適用于被稱為格的幾何對象，這些幾何對象是空間中的點集，其坐標通常具有整數值。
LLL算法解決了有關其屬性的一個基本問題：晶格中的哪個點最接近原點？這是一個通常很難解決的簡單問題，尤其是在高維空間中以及晶格中的點何時形成扭曲的形狀。
目前，唯一已知能夠承受量子計算機攻擊的加密系統正是基于 LLL 算法。
洛瓦茲榮獲過多個獎項，包括 1999 年沃爾夫獎、1999 年高德納獎、2001 年哥德爾獎和2010年京都獎。2007年至2010年，洛瓦茲擔任國際數學聯盟主席。他還于2014年至2020年擔任匈牙利科學院院長，在這些年里，他為阻止匈牙利政府接管該學院的研究機構而做出了大膽的努力，他和其他許多人認為，此舉將降低研究人員的獨立性。
遺憾的是，他們最終沒有成功。
自從2003年授予阿貝爾獎以來，洛瓦茲是第三位在匈牙利出生的人，而威格森則是第二位以色列人，獲獎者將獲得獎金約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
本文首發于微信公眾號：新智元。文章內容屬作者個人觀點，不代表和訊網立場。投資者據此操作，風險請自擔。
最新評論