[問卦] 2023圖靈獎公布 Avi Wigderson

https://awards.acm.org/about/2023-turing

美國電腦學會ACM決定將資工最高榮譽頒給以色列的Avi Wigderson。

"他重塑了我們對計算中隨機性作用的理解以及數十年來在理論計算機科學領域的學術領導 地位而受到認可。

" Wigderson是新澤西州普林斯頓高等研究院數學學院的赫伯特·H·馬斯教授。

他是計算複 雜性理論、演算法和最佳化、隨機性和密碼學、平行和分散式計算、組合學和圖論以及理 論計算機科學與數學和科學之間的聯繫等領域的領導者。

四十年來他一直是理論電腦科學研究的領導者，他為理解隨機性和偽隨機性在計算中的作 用做出了基礎性貢獻。

電腦科學家發現隨機性和計算難度（即識別沒有有效演算法的自然問題）之間存在顯著的 關聯。Wigderson與同事合作撰寫了一系列極具影響力的關於用硬度換取隨機性的著作。

他們證明在標準且廣泛相信的計算假設下，每個機率多項式時間演算法都可以有效地去隨 機化（即完全確定性）。

換句話說，隨機性對於高效率計算來說並不是必要的。 這一系 列作品徹底改變了我們對隨機性在計算中的作用的理解，以及我們思考隨機性的方式。

除了圖靈獎，Wigderson還獲得以下獎項:

1994 內萬林納獎(在電腦科學的數學方面有主要貢獻者):表彰他在計算複雜性理論的工作

2009 哥德爾獎(理論計算機科學領域傑出論文):表彰他在圖的鋸齒積方面的工作

2019 高德納獎(在計算機科學基礎做出傑出貢獻的人):表彰他對計算機科學在隨機計算、 密碼學、電路複雜性、證明複雜性、並行計算以及我們對圖的基本性質的理解所作的貢獻

2021 阿貝爾獎(數學界諾貝爾獎):表彰他對理論計算機科學和離散數學的基礎性貢獻，以 及他們將其塑造為現代數學的中心領域方面的領導作用

--