亚洲二区三区在线,久久久久高清毛片一级,亚洲综合一区二区三区不卡,中文不卡av

昨晚，美國計算機協會（ACM）宣布將 2023 年 ACM A.M. 圖靈獎授予數學家和頂級理論計算機科學家 Avi Wigderson，以表彰他對計算理論的奠基性貢獻，包括重塑我們對隨機性在計算中的作用的理解，以及他數十年來對理論計算機科學領域的引領。

ACM A.M. 圖靈獎由 ACM 于 1966 年設立，專門獎勵那些對計算機事業作出重要貢獻的個人。圖靈獎名稱取自計算機科學先驅、英國科學家 Alan M. Turing，這個獎設立目的之一正是為了紀念這位偉大的科學家。

圖靈獎對獲獎者要求極高，評獎程序極嚴，一般每年只獎勵一名計算機科學家，只有極少數年度有兩名在同一方向上做出貢獻的科學家同時獲獎。因此，圖靈獎也是計算機界最負盛名、最崇高的一個獎項，有 “計算機界的諾貝爾獎” 之稱。

什么是理論計算機科學？

理論計算機科學關注該領域的數學基礎。它提出的問題包括：“這個問題是否可以通過計算解決？”或“如果這個問題可以通過計算解決，那么需要多少時間和其他資源？” 理論計算機科學還探索高效算法的設計。

與我們生活息息相關的每一項計算技術都是通過算法實現的。了解強大高效算法的原理，不僅能加深我們對計算機科學的理解，還能加深我們對自然規律的理解。從密碼學和計算生物學到網絡設計、機器學習和量子計算，理論計算機科學的研究突破幾乎推動了該學科各個領域的進步。

為什么隨機性很重要？

從根本上說，計算機是確定性系統；應用于任何給定輸入的算法指令集唯一地決定了其計算，尤其是其輸出。換句話說，確定性算法遵循的是一種可預測的模式。相比之下，隨機性則缺乏明確的模式，或者說事件或結果缺乏可預測性。由于我們生活的世界中充滿了天氣系統、生物和量子現象等隨機事件，計算機科學家豐富了算法，允許它們在計算過程中做出隨機選擇，借此提高算法的效率。事實上，許多沒有已知高效確定性算法的問題，已經通過概率算法得到了高效解決，盡管存在一些小概率錯誤（可以有效減少）。

但是，隨機性是必不可少的，還是可以去除？概率算法成功所需的隨機性質量又如何？ 這些問題以及其他許多基本問題是理解計算中隨機性和偽隨機性的關鍵。加深對計算中隨機性動態的理解，可以幫助我們開發出更好的算法，并加深我們對計算本身性質的理解。

Wigderson 的貢獻

Wigderson 在計算復雜性理論、算法與優化、隨機性與密碼學、并行與分布式計算、組合學、圖論以及理論計算機科學與數學和科學之間的聯系等領域，一直處于引領地位。

四十年來，Wigderson 一直是計算機科學理論研究領域的引領人物，他在理解隨機性和偽隨機性在計算中的作用方面做出了奠基性的貢獻。

計算機科學家發現了隨機性與計算難度之間的顯著聯系（即確定沒有高效算法的自然問題）。Wigderson 與同事合作，撰寫了一系列極具影響力的關于用隨機性換取難度的著作。他們證明，在標準的、被廣泛相信的計算假設下，每一種概率多項式時間算法都可以有效地去隨機化（即完全確定）。

換句話說，隨機性并不是高效計算的必要條件。這一系列著作徹底改變了我們對隨機性在計算中的作用的理解，也改變了我們對隨機性的思考方式。這些影響深遠的論文包括以下三篇：

1）“Hardness vs. Randomness”（與 Noam Nisan 合著）。 除其他發現外，這篇論文還介紹了一種新型偽隨機發生器，并證明了在比以前已知的假設更弱的條件下，隨機算法的高效確定性模擬是可能的。

論文鏈接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

2）“BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs”（與 László Babai、Lance Fortnow 和 Noam Nisan 合著） 這篇論文利用“hardness amplification”證明，在較弱的假設條件下，有界錯誤概率多項式時間（BPP）可以在亞指數時間內模擬無限多的輸入長度。

論文鏈接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

3）“P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma”（與 Russell Impagliazzo 合著） 這篇論文介紹了一種更強的偽隨機發生器，它在硬度與隨機性之間實現了基本最優的權衡。

論文鏈接：https://dl.acm.org/doi/pdf/10.1145/258533.258590

重要的是，這三篇論文的影響遠遠超出了隨機性和反隨機化領域。這些論文中的觀點后來被應用于理論計算機科學的許多領域，并推動了該領域多位領軍人物發表具有影響力的論文。 后來，Wigderson 與 Omer Reingold、Salil Vadhan 和 Michael Capalbo 合作，仍然在計算隨機性的廣泛領域開展工作，在另一篇論文中首次提出了擴展圖的高效組合構造，擴展圖是一種稀疏圖，具有很強的連通性。它們在數學和理論計算機科學領域都有許多重要應用。

論文鏈接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf

除了在隨機性方面的研究之外，Wigderson 還是多驗證器交互式證明、密碼學和電路復雜性等理論計算機科學內多幾個領域的領袖。

受人尊敬的導師

除了開創性的技術貢獻，Wigderson 還是公認的受人尊敬的導師和同事，為無數年輕研究人員提供建議。廣博的知識和優秀的技術能力，加上友善、熱情和慷慨，讓他吸引了許多最優秀的年輕人投身于理論計算機科學領域。

“必須指出的是，Avi Wigderson 還獲得了阿貝爾獎（Abel Prize），該獎項被認為是數學領域終身成就最重要的榮譽，” ACM 主席 Yannis Ioannidis 說道。 “Avi Wigderson 在隨機性和其他課題方面的工作在過去三十年里為理論計算機科學制定了方向，” 谷歌高級副總裁 Jeff Dean 解釋說，“從計算機科學誕生之初，研究人員就認識到，隨機性是為各種應用設計更快算法的一種方法。為更好地理解隨機性所做的努力將繼續為我們的領域帶來重要益處，Wigderson 在這一領域開辟了新天地。”

Wigderson 的履歷

自 1999 年以來，Wigderson 一直擔任普林斯頓高等研究院數學學院赫伯特-H-馬斯教授。此前，他曾擔任耶路撒冷希伯來大學教授，并在普林斯頓大學、加州大學伯克利分校、IBM 等機構擔任客座教授。

Wigderson 畢業于以色列理工學院，并獲得普林斯頓大學計算機科學碩士、MSE 和博士學位。他獲得的榮譽包括阿貝爾獎、IMU 算盤獎、唐納德-E-克努特獎、Edsger W. Dijkstra 分布式計算獎和哥德爾獎。他是 ACM Fellow、美國國家科學院和美國藝術與科學院院士。

參考鏈接：https://awards.acm.org/about/2023-turing