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

※ 引述《ttucse ((((>(￣▽￣)<))))》之銘言：
: https://awards.acm.org/about/2023-turing
: 美國電腦學會ACM決定將資工最高榮譽頒給以色列的Avi Wigderson。
: "他重塑了我們對計算中隨機性作用的理解以及數十年來在理論計算機科學領域的學術領導 地位而受到認可。
: " Wigderson是新澤西州普林斯頓高等研究院數學學院的赫伯特·H·馬斯教授。
: 他是計算複 雜性理論、演算法和最佳化、隨機性和密碼學、平行和分散式計算、組合學和圖論以及理 論計算機科學與數學和科學之間的聯繫等領域的領導者。
: 四十年來他一直是理論電腦科學研究的領導者，他為理解隨機性和偽隨機性在計算中的作 用做出了基礎性貢獻。
: 電腦科學家發現隨機性和計算難度（即識別沒有有效演算法的自然問題）之間存在顯著的 關聯。Wigderson與同事合作撰寫了一系列極具影響力的關於用硬度換取隨機性的著作。
: 他們證明在標準且廣泛相信的計算假設下，每個機率多項式時間演算法都可以有效地去隨 機化（即完全確定性）。
: 換句話說，隨機性對於高效率計算來說並不是必要的。 這一系 列作品徹底改變了我們對隨機性在計算中的作用的理解，以及我們思考隨機性的方式。
: 除了圖靈獎，Wigderson還獲得以下獎項:
: 1994 內萬林納獎(在電腦科學的數學方面有主要貢獻者):表彰他在計算複雜性理論的工作: 2009 哥德爾獎(理論計算機科學領域傑出論文):表彰他在圖的鋸齒積方面的工作
: 2019 高德納獎(在計算機科學基礎做出傑出貢獻的人):表彰他對計算機科學在隨機計算、 密碼學、電路複雜性、證明複雜性、並行計算以及我們對圖的基本性質的理解所作的貢獻
: 2021 阿貝爾獎(數學界諾貝爾獎):表彰他對理論計算機科學和離散數學的基礎性貢獻，以 及他們將其塑造為現代數學的中心領域方面的領導作用

首先先介紹一種東西叫做邏輯閘，例如AND邏輯閘呢，就是輸入有兩根電線，兩根電線
都可以承載一個0或1的值，如果兩根電線都是1，這個邏輯閘才會輸出1，否則就輸出0，其它種邏輯閘就不贅述了。

有些計算問題被相信無法用小型電路解決，也就是你如果要用邏輯閘構成一個電路，
來解決這種問題，將會需要很多個邏輯閘才能辦到，這種信念叫做circuit lower
bound，是計算理論的大哉問，除了少數幾個知名的例子外，一般相信circuit lower
bound極難被證明。

另外一種問題是derandomization問題，也就是說如果你有一個會丟骰子的演算法可以
解決某種問題，是不是就一定可以換一個不用丟骰子、且執行時間也差不多的演算法，
來解決同樣的問題？這也是極難回答的。

Wigderson參與的一些研究證明了circuit lower bound跟derandomization問題本質上
是同一個問題，大概就4這樣。

不過當然，兩種問題都仍然是沒有人會回答的，只是知道兩者差不多等價。

南無阿彌陀佛。

--