2023年圖靈獎揭曉！普林斯頓數學教授，成史上首位阿貝爾獎雙料獲獎者

新智元報道

編輯：編輯部

【新智元導讀】2023年圖靈獎，剛剛頒給普林斯頓數學教授Avi Wigderson！作爲理論計算機科學領域的領軍人物，他對於理解計算中的隨機性和僞隨機性的作用，做出了開創性貢獻。

2023年圖靈獎揭曉！

獲得這屆「計算機界諾貝爾獎」——ACM A.M.圖靈獎的，是普林斯頓高等研究院數學學院的教授Avi Wigderson。

表彰的是Wigderson在計算理論領域的開創性貢獻，特別是他對計算中隨機性角色的重新定義，以及他在理論計算機科學領域數十年的引領。

最終，他將獲得高達100萬美元的獎金。

不僅如此，這一榮譽也使Avi Wigderson成爲了，歷史上第一位同時獲得圖靈獎和阿貝爾獎的人。

阿貝爾獎被視爲數學領域的最高榮譽

Wigderson是普林斯頓高級研究院數學學院的Herbert H. Maass教授。

他在計算複雜性理論、算法與優化、隨機性與密碼學、並行與分佈式計算、組合學和圖論等領域均有突出貢獻，並且在理論計算機科學與數學及科學的交叉領域中，也具有重要影響。

在此之前，Wigerson於2009年獲得了哥德爾獎； 2018年， 因對計算機科學和數學理論的貢獻（Institute for Advanced Study）當選ACM Fellow； 並於 2019年獲得了高德納獎。

計算中的隨機性和僞隨機性

過去四十年裡，Wigderson對於理解計算中的隨機性和僞隨機性，做出了開創性貢獻。

此前，計算機科學家們已經發現，隨機性與計算難度之間存在顯著的聯繫，比如，一些自然問題並沒有高效的算法解決方案。

而Wigderson與同事合作撰寫了一系列研究，通過增加計算難度，來減少算法中的隨機性需求。

這些研究，對於學界具有深遠的影響。

他們成功地證明了，在一些廣泛認可的計算假設下，所有的概率多項式時間算法，都可以被有效轉化爲確定性算法。

也即是說，高效的計算並不依賴於隨機性。

從此，我們對於計算中隨機性作用的理解被徹底改變。

以下就是三篇極具影響力的論文——

「Hardness vs. Randomness」（與Noam Nisan合著）

這篇論文不僅引入了一種新型僞隨機發生器，而且還證明了：在比以前所知更弱的假設下，可以對隨機算法進行高效確定性模擬。

「BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs」（與László Babai、Lance Fortnow和Noam Nisan合著）

這篇論文利用「難度放大」，證明了在弱假設下，可以在亞指數時間內模擬無限多輸入長度的有限錯誤概率多項式時間（BPP）。

「P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma」（與Russell Impagliazzo合著）

這篇論文介紹了一種更強的僞隨機發生器，它在本質上實現了難度與隨機性之間的最優權衡。

Wigderson的這三篇論文，其理論被廣泛應用於理論計算機科學的多個分支，並且激發了多位專家的重要研究。

在計算中隨機性的廣泛領域內，Wigderson與Omer Reingold、Salil Vadhan和Michael Capalbo合作，首次高效構造了展開圖，這些圖具有出色的稀疏性和連通性，廣泛應用於數學和理論計算機科學中。

上下滑動

除了隨機性研究，Wigderson還在多證明者交互式證明、密碼學和電路複雜度等多個理論計算機科學領域，發揮了重要的領導作用。

此外，他作爲導師和同事也備受讚譽。他的親和力、熱情和慷慨，吸引了衆多青年學者，投身理論計算機科學領域。

複雜性理論先驅

作爲一名計算複雜性理論家，相比於問題的答案，讓Avi Wigderson更感興趣的是，這些問題是否有解決方案？以及，該如何進行判斷？

「對於我們正在面對並嘗試解決的每一個問題，都不能排除存在一種能夠解決它的算法。這是我認爲最有趣的問題。」

如今，Wigderson憑藉着在計算理論基礎上的傑出貢獻，榮獲了公認的最高榮譽之一——ACM A.M.圖靈獎。

Wigderson的父親非常熱愛拼圖和數學基本原理。

而在以色列海法長大的Wigderson，深受父親的影響，

「他讓我對這個領域產生了濃厚的興趣，」Wigderson回憶道。

1970年代，Wigderson在海法大學開始了大學生涯。

最初他本主修數學，但在父母的建議下轉向了計算機科學。而這背後的原因很樸素——他的父母認爲，這個專業更好找工作。

雖然沒去成數學專業，但Wigderson很快就發現，計算機科學是一個充滿了未解之謎的領域，而這些謎題，本質上都與數學相關。

他早期的一項開創性工作，正是探討這樣一個看似矛盾的問題——

能否在不展示證明過程的情況下讓人相信：一個數學命題已經得到了證明？

1985年，Shafi Goldwasser、Silvio Micali和Charles Rackoff首次提出了零知識交互證明的概念，並展示了其在若干命題上的應用。

後來，Wigderson與Micali和Oded Goldreich一起進一步闡述了這一理論，明確了這一點——

如果一個命題可以被證明，那麼它也可以有一個零知識證明。

有了零知識證明，我們就可以證明自己使用密鑰正確加密或簽名了信息，同時不泄露任何相關的細節。

對此，普林斯頓大學的計算機科學家Ran Raz評價道：「Avi在密碼學領域有許多極其重要的成果，而這，就最重要的那個。」

不過，Wigderson最最具奠基性的成就，可能在於另一個領域：將計算難度與隨機性相聯繫。

到了1970年代末，計算機科學家們已經發現，對於許多難題，採用隨機性算法（也稱爲概率算法）會顯著優於傳統的確定性算法。

例如，1977年，Robert Solovay和Volker Strassen提出了一種隨機算法，可以比當時最好的確定性算法更快地判斷一個數字是否爲質數。

對某些問題而言，概率算法則可以引出確定性算法。

在1980年代初，Wigderson與加州大學伯克利分校的Richard Karp合作，將隨機性的思想應用於那些被認爲計算上極其困難的問題，也就是那些不存在已知的確定性算法能在合理時間內解決的問題。

很快，Wigderson和Karp就發現了一個難題的隨機算法，並最終成功將其轉化爲了確定性算法。

與此同時，其他研究人也展示了，如何在密碼學問題中通過計算難度的假設來實現去隨機化。

由此，Wigderson也和其他人一樣，開始質疑在有效解決問題時隨機性的必要性，以及在什麼條件下可以完全去除隨機性。

隨後他意識到，對隨機性的需求與問題的計算難度緊密相連。

在1994年的一篇論文中，Wigderson與計算機科學家Noam Nisan共同證明——

如果真如大多數計算機科學家所猜測的那樣，存在自然界中的困難問題，那麼，任何高效的隨機算法都可以被高效的確定性算法替代。

也就是說，隨機性總是可以被消除的。

更爲重要的是，他們發現確定性算法可能使用「僞隨機」序列——這些數據串看起來隨機，但實際上不是。

同時，他們還展示瞭如何利用任意難題來構建僞隨機生成器。即通過將僞隨機比特（不是真正的隨機比特）輸入到概率算法中，就可以爲同一問題生成一個高效的確定性算法。

Sudan指出，這篇論文幫助計算機科學家們認識到隨機性的不同程度，從而幫助揭示了難題的複雜性及其解決方法。「這其中的關鍵不僅僅是隨機性，而是對隨機性的認知，」他說。

如今，隨機性已經成爲複雜性理論中的一個強大工具，但它非常難以捉摸。

Wigderson指出，像硬幣擲出和骰子擲出這樣的行爲，並不是真正的隨機：如果你對這些物理系統有足夠的瞭解，那麼其結果是完全可以預測的。

但完美的隨機性既難以捉摸也難以驗證。

在過去幾十年裡，來自計算理論的發現幫助我們深入理解了許多意想不到的問題，從鳥羣的集體飛行、選舉結果到體內的生化反應。

最後，我們用Wigerson的一句話總結作爲總結——計算的應用無處不在。

「基本上，任何自然過程都可以被視爲一種演化的計算過程，因此我們可以從計算的角度來研究它。可以說，幾乎所有事物都在進行某種形式的計算。」

補充知識

什麼是理論計算機科學？

理論計算機科學專注於計算領域的數學基礎。

它探討的問題包括，「這個問題能否通過計算來解決？」，以及「如果這個問題可以通過計算解決，需要投入多少時間和其他資源？」

此外，理論計算機科學還致力於設計高效的算法。每一項觸及我們生活的計算技術都是通過算法實現的。

深入理解構成強大和高效算法的原理，不僅能增進我們對計算機科學的認識，還能幫助我們更好地理解自然規律。

儘管理論計算機科學以其提供的激動人心的智力挑戰而聞名，且通常不直接關注計算的實際應用改進，但該領域的研究成果已在從密碼學、計算生物學到網絡設計、機器學習及量子計算等幾乎所有子領域推動了顯著進展。

爲什麼隨機性很重要？

一般來說，計算機是確定性系統——算法的指令集對任何特定輸入都有唯一確定的計算過程和輸出結果。

也就是說，確定性算法遵循一個可預測的模式。

然而，隨機性則不同，它沒有明確的模式，也無法預測事件或結果的發生。

鑑於我們所處的世界似乎充斥着隨機事件（如天氣系統、生物和量子現象等），計算機科學家們通過讓算法在計算過程中進行隨機選擇，以期提高算法的效率。

事實上，許多以前沒有有效的確定性算法解決方案的問題，現在通過概率算法得到了有效的解決，雖然這些算法可能會有小概率的錯誤（但這種錯誤可以有效地減少）。

但是，隨機性是否是必要的，還是可以去除它？成功的概率算法需要什麼樣的隨機性？

這些問題以及其他許多基本問題構成了理解計算中隨機性和僞隨機性的核心。

更深入地理解計算中隨機性的動態可以幫助我們開發更優秀的算法，並深化我們對計算本質的理解。

參考資料：

https://www.acm.org/

https://awards.acm.org/turing

https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/

https://www.ias.edu/news/avi-wigderson-2023-acm-am-turing-award