今天,ACM官方公布了2019年高德納獎(jiǎng)和哥德爾獎(jiǎng)的得主,分別表彰Avi Wigderson對(duì)計(jì)算隨機(jī)性的革命性理解和Irit Dinur對(duì)PCP定理的基礎(chǔ)性工作。高德納獎(jiǎng)和哥德爾獎(jiǎng)是理論計(jì)算機(jī)科學(xué)界兩大極富盛譽(yù)的獎(jiǎng)項(xiàng)。
ACM算法與計(jì)算理論興趣組(SIGACT)今天宣布,2019年高德納獎(jiǎng)授予普林斯頓大學(xué)高等研究院教授Avi Wigderson,哥德爾獎(jiǎng)授予以色列威茨曼研究所的Irit Dinur教授。Wigderson和Dinur將在第51屆計(jì)算理論年會(huì)(STOC 2019)上正式獲獎(jiǎng)。
高德納獎(jiǎng)(Donald E. Knuth Prize)
普林斯頓大學(xué)高等研究院Avi Wigderson教授獲得2019年高德納獎(jiǎng),表彰他在隨機(jī)計(jì)算、密碼學(xué)、電路復(fù)雜度、證明復(fù)雜度、并行計(jì)算等計(jì)算機(jī)科學(xué)基礎(chǔ)領(lǐng)域做出的基礎(chǔ)性和持久的貢獻(xiàn),以及對(duì)基本圖形屬性理解的貢獻(xiàn)。
Avi Wigderson
在一系列研究成果中,Wigderson證明,在人們普遍認(rèn)可的計(jì)算假設(shè)下,每個(gè)概率多項(xiàng)式時(shí)間算法都可以完全去隨機(jī)化(derandomized)。換句話說,多項(xiàng)式時(shí)間計(jì)算不需要隨機(jī)性。在密碼學(xué)領(lǐng)域,Wigderson與人合著了兩篇具有里程碑意義的論文,論證了如何在不誠(chéng)實(shí)的參與者面前安全地計(jì)算任何函數(shù)。他也是一個(gè)團(tuán)隊(duì)的一員,這個(gè)團(tuán)隊(duì)展示了所有短證明問題(NP中的所有問題)實(shí)際上都有零知識(shí)證明:即證明只產(chǎn)生其有效性的證據(jù),一個(gè)中心密碼結(jié)構(gòu)。
Wigderson于1983年在普林斯頓大學(xué)獲得博士學(xué)位。隨后,他在加州大學(xué)伯克利分校擔(dān)任客座助理教授,在IBM擔(dān)任訪問科學(xué)家,并在伯克利的數(shù)學(xué)科學(xué)研究所(MSRI)擔(dān)任研究員,1986年加入希伯來大學(xué)(Hebrew University)擔(dān)任教員。自1999年以來,Wigderson一直是高等研究院數(shù)學(xué)學(xué)院的教授。Wigderson還在2009年獲得哥德爾獎(jiǎng)(Godel Prize),獲獎(jiǎng)原因是他與Omer Reingold和Salil Vadhan合作的工作,并在1994年獲得了內(nèi)萬(wàn)林納獎(jiǎng)(Nevanlinna Prize)。
Avi Wigderson還是阿里巴巴達(dá)摩院學(xué)術(shù)委員會(huì)的十位頂尖科學(xué)家之一。
高德納獎(jiǎng)旨在表彰個(gè)人對(duì)計(jì)算機(jī)科學(xué)基礎(chǔ)的杰出貢獻(xiàn),以及他們?cè)谠擃I(lǐng)域長(zhǎng)期的整體影響。高德納獎(jiǎng)的命名取自斯坦福大學(xué)的高德納 (Donald Knuth),他被稱為 “算法分析之父”。該獎(jiǎng)項(xiàng)由 ACM 算法與計(jì)算理論特別興趣組 (SIGACT) 和 IEEE 計(jì)算機(jī)學(xué)會(huì)計(jì)算數(shù)學(xué)基礎(chǔ)技術(shù)委員會(huì) (TCMF) 聯(lián)合頒發(fā)。
哥德爾獎(jiǎng)(G?del Prize)
2019年哥德爾獎(jiǎng)授予以色列威茨曼研究所的Irit Dinur教授,表彰她在“The PCP Theorem by Gap Amplification”論文中證明了PCP定理。
Irit Dinur
PCP定理是計(jì)算理論中最具影響力的結(jié)果之一,對(duì)研究近似問題的固有難度和概率證明系統(tǒng)研究都具有重要的意義。Dinur的論文提供了PCP定理的另一種證明,它與原來的證明有本質(zhì)的不同。她的新證明比原來的證明簡(jiǎn)單得多,使其在復(fù)雜性課程中的演示成為一項(xiàng)可行的任務(wù)。此外,該證明顯著改進(jìn)了所得PCP的重要參數(shù),對(duì)本地可測(cè)試代碼產(chǎn)生了相同的改進(jìn),并激發(fā)了包括實(shí)際應(yīng)用在內(nèi)的許多研究。為如此重要的結(jié)果提供另一種證明是一項(xiàng)重大成就,特別是該證明解決了許多研究人員感到困惑的問題,并解決了該領(lǐng)域的一個(gè)中心開放問題。
Dinur在特拉維夫大學(xué)獲得博士學(xué)位。之后,她先后在普林斯頓高等研究院、NEC和加州大學(xué)伯克利分校任職,之后加入以色列魏茨曼科學(xué)研究所擔(dān)任計(jì)算機(jī)科學(xué)教授。Dinur還獲得了Anna and Lajos Erd?s Prize數(shù)學(xué)獎(jiǎng)(2012年)和布魯諾紀(jì)念獎(jiǎng)(2007)。
哥德爾獎(jiǎng)表彰對(duì)數(shù)學(xué)邏輯和計(jì)算機(jī)科學(xué)基礎(chǔ)的重大貢獻(xiàn)。該獎(jiǎng)項(xiàng)以1906年出生在奧匈帝國(guó)(現(xiàn)捷克共和國(guó))的庫(kù)爾特·哥德爾(Kurt G?del)命名。哥德爾的工作對(duì)20世紀(jì)的科學(xué)和哲學(xué)思想產(chǎn)生了巨大的影響。哥德爾獎(jiǎng)由ACM SIGACT和歐洲理論計(jì)算機(jī)科學(xué)協(xié)會(huì)(EATCS)聯(lián)合頒發(fā)。
-
計(jì)算機(jī)科學(xué)
+關(guān)注
關(guān)注
1文章
144瀏覽量
11547 -
ACM
+關(guān)注
關(guān)注
0文章
35瀏覽量
10521
原文標(biāo)題:2019高德納獎(jiǎng)、哥德爾獎(jiǎng)公布!阿里達(dá)摩院、以色列科學(xué)家獲獎(jiǎng)
文章出處:【微信號(hào):AI_era,微信公眾號(hào):新智元】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
海格通信三個(gè)項(xiàng)目入選2024年度廣東省科學(xué)技術(shù)獎(jiǎng)
升譜光電榮獲2025阿拉丁神燈獎(jiǎng)全國(guó)優(yōu)秀照明獎(jiǎng)

上汽集團(tuán)榮膺2024年度上海市“銀鴿獎(jiǎng)”優(yōu)勝獎(jiǎng)
中國(guó)中車榮獲2024年度中國(guó)鐵道學(xué)會(huì)科學(xué)技術(shù)獎(jiǎng)
德賽電池榮膺立訊精密“優(yōu)質(zhì)配合獎(jiǎng)”
德賽西威榮獲長(zhǎng)安汽車2024年度“戰(zhàn)略生態(tài)獎(jiǎng)”
德賽電池榮獲2024高工金球獎(jiǎng)年度標(biāo)桿項(xiàng)目獎(jiǎng)
電裝榮獲2024年度扶輪獎(jiǎng)“可持續(xù)發(fā)展標(biāo)桿獎(jiǎng)”
德賽西威榮獲高工金球獎(jiǎng)“年度量產(chǎn)首創(chuàng)獎(jiǎng)”
天馬榮獲vivo 2024年度“優(yōu)秀質(zhì)量獎(jiǎng)”和“最佳交付獎(jiǎng)”
晶能光電榮獲行家極光獎(jiǎng)“2024年度優(yōu)秀產(chǎn)品獎(jiǎng)”
睿創(chuàng)微納榮獲第六屆“金輯獎(jiǎng)”最佳技術(shù)實(shí)踐應(yīng)用獎(jiǎng)
晶科能源李仙德榮獲“2023年度金牛卓越企業(yè)家獎(jiǎng)”
奧迪威榮獲“持續(xù)15年高新技術(shù)企業(yè)”卓越成就獎(jiǎng)

評(píng)論