2021年阿貝爾獎獲得者László Lovász。圖片來源：Hungarian Academy of Sciences/Laszlo Mudra

上個世紀70年代，當 Avi Wigderson 和 László Lovász 開始他們的職業生涯時，理論計算機科學和純數學幾乎是完全分開的學科領域。經過幾十年的發展，這兩個學科之間早已變得極為密切，我們甚至很難分清它們之間的界限。今天，Wigderson和Lovász二人因其在理論計算機科學和離散數學所作出的基礎性貢獻，獲得了數學領域的最高獎之一——阿貝爾獎。

編譯 | 佐 佑

● 　● 　●

1

理論計算機科學研究的是計算的能力和侷限，其根源可追溯到庫爾特·哥德爾、阿隆佐·丘奇、阿蘭·圖靈，以及約翰·馮·諾伊曼的基礎工作，這些工作為真正的物理計算機研究的發展奠定了堅實的基礎。

理論計算機科學包含了兩個互補的子學科，一個是演算法設計，另一個是計算複雜性。前者涉及到為大量的計算問題開發有效的方法，後者展示了演算法效率存在固有的侷限性。20世紀60年代，Alan Cobham 等人提出了多項式時間演算法的概念，Stephen Cook 等人提出了著名的P≠NP猜想。這些工作對整個領域以及Lovász和Wigderson的工作，都產生了重大影響。

理論計算機科學是密碼學的基礎，且它對其他一些科學領域的影響正日漸明顯。圖形、字串、排列等離散結構都是理論計算機科學的核心，離散數學和理論計算機科學也自然成了緊密相關的領域。雖然這兩個領域都從傳統的數學領域中獲益良多，但現在反向的影響也越來越大。理論計算機科學所帶來的應用、概念和技術，激發了更多新的挑戰，開闢了新的研究方向，並解決了純數學和應用數學中的一些重要的未解難題。

在過去的幾十年裡，Lovász和Wigderson一直是這一領域中的領軍人物。他們的工作在許多方面都有交叉，尤其是他們都為理解計算中的隨機性，以及探索高效計算的邊界，做出了傑出貢獻。

2

1948年，Lovász出生於匈牙利布達佩斯。年輕時的Lovász就已是數學界的一顆閃耀新星，他在十幾歲時就在國際數學奧林匹克競賽上獲得了三枚金牌。

Lovász最具影響力的成果之一，就是與Arjen Lenstra和Hendrik Lenstra 一起創立了以他們三人名字命名的LLL演算法。這是最基本的演算法之一，它不僅在理論上很重要，在很多實際用途上也很重要。LLL演算法適用於被稱為格的幾何物件，格指的是在空間中其座標值通常為整數值的點集。LLL演算法解決了關於格的屬性的一個基本問題：格中的哪個點離原點最近？這是一個難以解決的問題，尤其是在高維空間中，以及格中的點會形成失真的形狀時。

LLL演算法不能精確地解答這個問題，但卻能找到一個很好的近似。它能確定一個點，並保證沒有其他任何點比這個點更接近原點。這一幾何模型有著廣泛的適用性，找到這個點在許多應用場景中都有重要意義。LLL演算法除了能分解有理多項式等應用之外，它還是密碼專家最喜歡的工具，它已成功地破解了幾個密碼系統。而令人稱奇的是，對LLL演算法的分析也能被用於設計和保證更新的基於格的密碼系統（甚至可抵擋量子計算機的攻擊）的安全性。

LLL演算法只是Lovász眾多有遠見的貢獻之一。除了LLL演算法，這位高產的數學家還證明了區域性引理；展示瞭如何有效地解決半定規劃，由此引領了一場演算法設計的革命；他為隨機漫步理論及其在歐幾里得等周問題和高維物體近似體積計算中的應用做出了貢獻；他與 Uriel Feige 等人發表的論文證明了一個早期版本的機率可檢測證明定理（PCP定理）；他還解決了長期存在的完美圖猜想、Kneser猜想等問題，並在近年來發展了圖極限理論。

3

2021年阿貝爾獎獲得者 Avi Wigderson 來源：Dan Komoda/Institute for Advanced Study, Princeton, NJ USA

Wigderson於1956年出生在以色列海法。在他十幾歲時，計算機科學家們才剛剛開始勾畫複雜性理論的基本框架。複雜性理論關注的是演算法的速度和效率，它涉及到根據演算法解決計算問題時的難度對問題進行分類。

Wigderson對計算複雜性的各個方面都做出了廣泛而深刻的貢獻，尤其是隨機性在計算中的作用。在過去的幾十年裡，一些研究人員為許多問題發展了確定性演算法，而此前只有隨機演算法是已知的。由Agrawal等人提出的確定性演算法的素數檢測就是去隨機化演算法的一個顯著例子。

這樣的去隨機化的成果，讓數學家們開始思考隨機性是否真的重要的問題。在20世紀90年代發表的兩篇論文中，Wigderson和他的合作者證明了在特定的假設下，答案很可能是否定的。他們提出了一個有點類似於P≠NP的猜想，P=BPP，這個等式意味著每個隨機演算法都可以被去隨機化，並轉化為具有可觀效率的確定性演算法；此外，去隨機化是通有且普遍的，它不依賴於隨機化演算法的內部細節。

另一種看待這項工作的方式是將其視為難度和隨機性之間的權衡：如果存在一個足夠困難的問題，那麼隨機性就可以透過高效的確定性演算法進行模擬。Wigderson隨後證明了與之相反的觀點，他得出的結論認為：即使是針對具有已知隨機演算法的特定問題的有效確定性演算法，也意味著一定存在這樣一個困難問題。

這一工作與偽隨機（看起來隨機）的物件緊密相關。Wigderson的工作構建了偽隨機生成器，它將幾個真正隨機的位元變成許多偽隨機位元，從一個不完美的隨機源中提取出近乎完美的隨機位元。他與 Omer Reingold 以及 Salil Vadhan 一起發展出的鋸齒形圖積，啟發了 Irit Dinur 對PCP定理的組合證明，以及Reingold對圖連通性問題的高效儲存演算法。

Wigderson的貢獻還不止於此，他對密碼學基礎的貢獻，為無需透過任何物理手段發展出像線上撲克遊戲一樣複雜的協議奠定了基礎。他在互動式證明系統方面的研究，尤其是在 “零知識證明” 這一悖論式的概念上的研究，最近已經被用於區塊鏈技術和數字貨幣上。工業、醫藥、線上通訊、電子商務和經濟中的數字創新，全部都依賴於演算法和複雜性理論的研究。

這些想法徹底改變了科學領域，而這僅僅是個開始。像Wigderson和Lovász這樣的學者將繼續對這些基礎性問題及其潛在影響進行研究。在Lovász和Wigderson的領導下，離散數學和相對年輕的理論計算機科學領域現正在逐漸成為現代數學的中心。

參考資料：

https://www.abelprize.no