※ 本文轉寄自 ptt.cc, 文章原始頁面
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這樣。
不過當然,兩種問題都仍然是沒有人會回答的,只是知道兩者差不多等價。
南無阿彌陀佛。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.138.155.129 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1713377704.A.8E0.html
Re: 回文串
46
[問卦] 2023圖靈獎公布 Avi Wigderson
Gossiping04/10 22:49
621
> Re: [問卦] 2023圖靈獎公布 Avi Wigderson
Gossiping04/18 02:15
21 則留言
sufferlove 作者的近期文章
Re: [問卦] 「優化」算支語嗎?
「最佳化」大概真的要老人才有聽過了。 本魯以前念書的時候,還聽過數學系「組合最佳化」課程(當時還沒人在講優化), 英文應該是combinatorial optimization,這東東基本上就是一個天才的感覺,每一 個定理都蘊含一個很難想到
Re: [問卦] 玉皇大帝是鄭成功???
※ 引述《yahe0526 (慕村拓哉)》之銘言: : 如題 : 前幾天聽到有人說 : 玉皇大帝是採輪值制的 : 前一任是關聖帝君 : 而現任是 鄭成功 : 但本魯很好奇啊 : 這件事到底是誰說的呢 : Google了一下 好像只有中華鄭成
Re: [問卦] 黃乙玲唱現場會不會太扯?
※ 引述《Mentor (曼陀)》之銘言: : 如題R : 剛剛無意間看到黃乙玲以前的演唱會影片 : 這live的實力會不會太扯 重點是我發現她沒有戴監聽耳機 : 唱得跟CD播出來根本一樣 : 這樣不會太扯嗎 : https://www.y
Re: [問卦] 沒人發現父母的智商比學區更重要嗎!
※ 引述《nobody0303 ()》之銘言: : 台灣一堆父母 : 明明就住在距離明星學區很遠的地方 : 結果卻硬要讓小孩跨學區就讀 : 不是在附近買奈米房型 : 全家人擠在裡面 : 不然就是花錢寄戶籍 : 每天長距離通勤 : 以為這樣小
推
推
→
→
推
推
推
推
→
→
→
→
→
→
→
→
→
→
→
→
→