2023年圖靈獎揭曉！普林斯頓數學教授，成史上首位阿貝爾獎雙料獲獎者
2023年圖靈獎，剛剛揭曉！
獲得這屆「計算機界諾貝爾獎」——ACM A.M.圖靈獎的，就是普林斯頓高等研究院數學學院的教授Avi Wigderson。
表彰的是Wigderson在計算理論領域的開創性貢獻，特別是他對計算中隨機性角色的重新定義，以及他在理論計算機科學領域數十年的引領。
不僅如此，這一榮譽也使Avi Wigderson成為了，歷史上第一位同時獲得圖靈獎和阿貝爾獎的人。
阿貝爾獎被視為數學領域的最高榮譽
Wigderson是普林斯頓高級研究院數學學院的Herbert H. Maass教授。
他在計算復雜性理論、算法與優化、隨機性與密碼學、并行與分布式計算、組合學和圖論等領域均有突出貢獻，并且在理論計算機科學與數學及科學的交叉領域中，也具有重要影響。
最終，他將獲得高達100萬美元的獎金。
計算中的隨機性和偽隨機性
過去四十年里，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的一句話總結作為總結——計算的應用無處不在。
「基本上，任何自然過程都可以被視為一種演化的計算過程，因此我們可以從計算的角度來研究它。可以說，幾乎所有事物都在進行某種形式的計算。」
Wigerson還曾在2009年獲得了哥德爾獎。
2018年，Wigerson因對計算機科學和數學理論的貢獻（Institute for Advanced Study）當選ACM Fellow。他還在2019年獲得了高德納獎。
補充知識
什么是理論計算機科學？
理論計算機科學專注于計算領域的數學基礎。
它探討的問題包括，「這個問題能否通過計算來解決？」，以及「如果這個問題可以通過計算解決，需要投入多少時間和其他資源？」
此外，理論計算機科學還致力于設計高效的算法。每一項觸及我們生活的計算技術都是通過算法實現的。
深入理解構成強大和高效算法的原理，不僅能增進我們對計算機科學的認識，還能幫助我們更好地理解自然規律。
盡管理論計算機科學以其提供的激動人心的智力挑戰而聞名，且通常不直接關注計算的實際應用改進，但該領域的研究成果已在從密碼學、計算生物學到網絡設計、機器學習及量子計算等幾乎所有子領域推動了顯著進展。
為什么隨機性很重要？
一般來說，計算機是確定性系統——算法的指令集對任何特定輸入都有唯一確定的計算過程和輸出結果。
也就是說，確定性算法遵循一個可預測的模式。
然而，隨機性則不同，它沒有明確的模式，也無法預測事件或結果的發生。
鑒于我們所處的世界似乎充斥著隨機事件（如天氣系統、生物和量子現象等），計算機科學家們通過讓算法在計算過程中進行隨機選擇，以期提高算法的效率。
事實上，許多以前沒有有效的確定性算法解決方案的問題，現在通過概率算法得到了有效的解決，雖然這些算法可能會有小概率的錯誤（但這種錯誤可以有效地減少）。
但是，隨機性是否是必要的，還是可以去除它？成功的概率算法需要什么樣的隨機性？
這些問題以及其他許多基本問題構成了理解計算中隨機性和偽隨機性的核心。
更深入地理解計算中隨機性的動態可以幫助我們開發更優秀的算法，并深化我們對計算本質的理解。
本文轉自 新智元 ，作者：新智元
