科學報科學文摘探索

曾被「純」數學家看不起的研究摘得2021年阿貝爾獎

字體大小：
更新日期：2022年2月14日
文章欄目：
文章標籤：

從互聯網安全到網絡研究的種種應用都離不開László Lovász和Avi Wigderson兩位得獎者的工作。 
計算理論領域的兩名先驅獲得了2021年阿貝爾獎。 阿貝爾獎是數學界的最高榮譽之一。 
當地時間3月17日，挪威科學與文學院宣布2021年阿貝爾獎被授予匈牙利數學家László Lovász和以色列計算機科學家Avi Wigderson，以表彰「他們在理論計算科學和離散數學作出的奠基性貢獻，以及將這兩個領域發展為現代數學核心方面的引領作用」。 兩人將分享750萬挪威克朗（約合580萬人民幣）的獎金。

László Lovász（左）和Avi Wigderson共同獲得2021年阿貝爾獎。 來源：（左）Hungarian Academy of Sciences/Laszlo Mudra/AbelPrize；（右）Cliff Moore/Institute for Advanced Study， Princeton/AbelPrize
目前就職於美國普林斯頓高等研究院（IAS）的Wigderson告訴《自然》，這次獲獎的是整個計算理論，而不僅僅是他本人的工作。 他說：「我覺得這對整個領域都極其重要。 」
目前就職於匈牙利羅蘭大學的Lovász說：「今天，想要分辨純數學和應用數學越來越難了——我覺得這是個好的發展。 」
算法從古希臘開始就是數學的核心，小學生在校學的簡單長除法也屬於算法。 但是從20世紀計算機誕生以來，算法研究的側重點就從「有算法能解決這個問題嗎？」變成了「有算法能在真正的計算機上用合理的時間解決這個問題嗎？至少是從理論上？」
Lovász和Wigderson在這些算法的發展中起到了關鍵作用，普林斯頓高等研究院的數論學家Peter Sarnak說：「算法的複雜性理論以及對解決問題速度的研究分別是在上世紀60年代和70年代確立的，而這兩位絕對屬於開宗立派的人物。 」
　　從數學到計算
Lovász於1948年出生在布達佩斯，他的成長環境鼓勵超常兒童參加難度很大的解題比賽。 他的早期靈感大多來源於Paul Erdős——現代曆史上最多產的數學家。 Erdős的工作主要是關於離散物體（例如網絡中的節點）及其關系的數學，而非幾何學等領域中常見的連續變量，Alfréd Rényi數學研究所的數學家Péter說。 
Lovász的職業生涯剛起步時，曾經被「純」數學家看不起的網絡理論等離散數學領域正變得重要起來——無論是對數學的其他領域還是對「大數據」分析等應用都變得日益重要。 他對於基礎研究及其應用都很感興趣。 在入職學術界前，他曾在微軟做了7年的全職研究員。 他解決了數學網絡理論的一些重要問題，例如在保證相鄰節點是不同顏色的前提下，有多少種給節點塗色的可能方法。 
Lovász最著名的成果之一是他與荷蘭數論學家Arjen Lenstra和Hendrik Lenstra兩兄弟共同設計出的算法。 該算法被稱為LLL算法，可以將一個大的整數向量分解成幾個最短的向量之和。 該算法在不同的純數學領域都有應用，已經成為數據加密研究中的重要一環。 基於整數向量的密鑰被看作是保障未來互聯網安全的希望所在，因為和現在常用的密鑰不同，基於整數向量的密鑰被認為不會被未來的量子計算機破解。 
Lovász於2007-2010年任國際數學聯合會主席。 他還在2014-2020年任匈牙利科學院院長，並在任期內勇於反對匈牙利政府接管科學院下的研究所，但最終未能成功。 包括他在內的很多人都認為，政府的接管會影響研究人員的獨立性。 
　　從計算到數學
Wigderson於1956年出生於以色列海法。 他在以色列和美國完成學業後曾入職多個學術機構，並於1999年加入普林斯頓高等研究院並任職至今。 阿貝爾獎在獲獎理由中認可了他在幾乎所有計算機科學領域的貢獻。 在這些領域中，他動用了所有能用上的數學工具解決各種各樣的問題，甚至是與他研究內容相距甚遠的領域。 Wigderson對他的領域非常有熱情，這種熱情具有「傳染性」，Sarnak說。 「當他和你說話時，你會覺得‘天啊，我最好把手頭上的工作放下，改為研究這個’。 」
Wigderson最知名的成就之一是闡明了隨機性在計算中的作用。 在很多情況下，比如尋找迷宮的出口，擲骰子往往能讓算法更快地找到解答，但具體原因還不是很清楚。 Sarnak說：「如果允許程序進行這種隨機選擇，那麼很多程序都能快很多。 」
Wigderson與合作者在90年代證明，如果使用了隨機性的算法看起來很高效，那麼必定存在另一種同樣高效的非隨機算法。 這從理論上確保了隨機算法確實可以找到正確的解答。 
Wigderson的另一項重要成果也在信息經濟學中發揮著越來越大的影響力。 這裏要涉及「零知識證明」（zero-knowledge proofs）——這種證明方式可以讓一個人在不透露某個論斷內容的情況下，證明這條論斷的正確性 。 
零知識證明對認證比特幣一類的數字貨幣非常重要，還可以幫助驗證一個人的身份。 也就是說，驗證方可以用一系列問題來讓對方提供「我知道正確密碼」的零知識證明，而不需透露具體密碼。 1991年，Wigderson與合作者證明，本質上所有數學論述都可以改寫成支持零知識證明的版本——Wigderson認為，「這可能他最令人驚訝、也最矛盾的結果」。 
自從2003年阿貝爾獎創立以來，Lovász是該獎項第三位出生於匈牙利的獲獎者，Wigderson是第二位以色列獲獎者。 除了2019年的Karen Keskulla Uhlenbeck外，阿貝爾獎的獲獎者全為男性。

本文朗讀完畢，請繼續下一頁。喜歡、科學報 cn-n.net 的內容，請記得按讚、收藏及分享！

從互聯網安全到網絡研究的種種應用都離不開László Lovász和Avi Wigderson兩位得獎者的工作。

計算理論領域的兩名先驅獲得了2021年阿貝爾獎。阿貝爾獎是數學界的最高榮譽之一。

當地時間3月17日，挪威科學與文學院宣布2021年阿貝爾獎被授予匈牙利數學家László Lovász和以色列計算機科學家Avi Wigderson，以表彰「他們在理論計算科學和離散數學作出的奠基性貢獻，以及將這兩個領域發展為現代數學核心方面的引領作用」。兩人將分享750萬挪威克朗（約合580萬人民幣）的獎金。

目前就職於美國普林斯頓高等研究院（IAS）的Wigderson告訴《自然》，這次獲獎的是整個計算理論，而不僅僅是他本人的工作。他說：「我覺得這對整個領域都極其重要。」

目前就職於匈牙利羅蘭大學的Lovász說：「今天，想要分辨純數學和應用數學越來越難了——我覺得這是個好的發展。」

算法從古希臘開始就是數學的核心，小學生在校學的簡單長除法也屬於算法。但是從20世紀計算機誕生以來，算法研究的側重點就從「有算法能解決這個問題嗎？」變成了「有算法能在真正的計算機上用合理的時間解決這個問題嗎？至少是從理論上？」

Lovász和Wigderson在這些算法的發展中起到了關鍵作用，普林斯頓高等研究院的數論學家Peter Sarnak說：「算法的複雜性理論以及對解決問題速度的研究分別是在上世紀60年代和70年代確立的，而這兩位絕對屬於開宗立派的人物。」

　　從數學到計算

Lovász於1948年出生在布達佩斯，他的成長環境鼓勵超常兒童參加難度很大的解題比賽。他的早期靈感大多來源於Paul Erdős——現代曆史上最多產的數學家。Erdős的工作主要是關於離散物體（例如網絡中的節點）及其關系的數學，而非幾何學等領域中常見的連續變量，Alfréd Rényi數學研究所的數學家Péter說。

Lovász的職業生涯剛起步時，曾經被「純」數學家看不起的網絡理論等離散數學領域正變得重要起來——無論是對數學的其他領域還是對「大數據」分析等應用都變得日益重要。他對於基礎研究及其應用都很感興趣。在入職學術界前，他曾在微軟做了7年的全職研究員。他解決了數學網絡理論的一些重要問題，例如在保證相鄰節點是不同顏色的前提下，有多少種給節點塗色的可能方法。

Lovász最著名的成果之一是他與荷蘭數論學家Arjen Lenstra和Hendrik Lenstra兩兄弟共同設計出的算法。該算法被稱為LLL算法，可以將一個大的整數向量分解成幾個最短的向量之和。該算法在不同的純數學領域都有應用，已經成為數據加密研究中的重要一環。基於整數向量的密鑰被看作是保障未來互聯網安全的希望所在，因為和現在常用的密鑰不同，基於整數向量的密鑰被認為不會被未來的量子計算機破解。

Lovász於2007-2010年任國際數學聯合會主席。他還在2014-2020年任匈牙利科學院院長，並在任期內勇於反對匈牙利政府接管科學院下的研究所，但最終未能成功。包括他在內的很多人都認為，政府的接管會影響研究人員的獨立性。

　　從計算到數學

Wigderson於1956年出生於以色列海法。他在以色列和美國完成學業後曾入職多個學術機構，並於1999年加入普林斯頓高等研究院並任職至今。阿貝爾獎在獲獎理由中認可了他在幾乎所有計算機科學領域的貢獻。在這些領域中，他動用了所有能用上的數學工具解決各種各樣的問題，甚至是與他研究內容相距甚遠的領域。Wigderson對他的領域非常有熱情，這種熱情具有「傳染性」，Sarnak說。「當他和你說話時，你會覺得‘天啊，我最好把手頭上的工作放下，改為研究這個’。」

Wigderson最知名的成就之一是闡明了隨機性在計算中的作用。在很多情況下，比如尋找迷宮的出口，擲骰子往往能讓算法更快地找到解答，但具體原因還不是很清楚。Sarnak說：「如果允許程序進行這種隨機選擇，那麼很多程序都能快很多。」

Wigderson與合作者在90年代證明，如果使用了隨機性的算法看起來很高效，那麼必定存在另一種同樣高效的非隨機算法。這從理論上確保了隨機算法確實可以找到正確的解答。

Wigderson的另一項重要成果也在信息經濟學中發揮著越來越大的影響力。這裏要涉及「零知識證明」（zero-knowledge proofs）——這種證明方式可以讓一個人在不透露某個論斷內容的情況下，證明這條論斷的正確性。

零知識證明對認證比特幣一類的數字貨幣非常重要，還可以幫助驗證一個人的身份。也就是說，驗證方可以用一系列問題來讓對方提供「我知道正確密碼」的零知識證明，而不需透露具體密碼。1991年，Wigderson與合作者證明，本質上所有數學論述都可以改寫成支持零知識證明的版本——Wigderson認為，「這可能他最令人驚訝、也最矛盾的結果」。

自從2003年阿貝爾獎創立以來，Lovász是該獎項第三位出生於匈牙利的獲獎者，Wigderson是第二位以色列獲獎者。除了2019年的Karen Keskulla Uhlenbeck外，阿貝爾獎的獲獎者全為男性。