今天，ACM官方公布了2019年高德納獎和哥德爾獎的得主，分別表彰Avi Wigderson對計(jì)算隨機(jī)性的革命性理解和Irit Dinur對PCP定理的基礎(chǔ)性工作。高德納獎和哥德爾獎是理論計(jì)算機(jī)科學(xué)界兩大極富盛譽(yù)的獎項(xiàng)。

ACM算法與計(jì)算理論興趣組(SIGACT)今天宣布，2019年高德納獎授予普林斯頓大學(xué)高等研究院教授Avi Wigderson，哥德爾獎授予以色列威茨曼研究所的Irit Dinur教授。Wigderson和Dinur將在第51屆計(jì)算理論年會(STOC 2019)上正式獲獎。

高德納獎(Donald E. Knuth Prize)

普林斯頓大學(xué)高等研究院Avi Wigderson教授獲得2019年高德納獎，表彰他在隨機(jī)計(jì)算、密碼學(xué)、電路復(fù)雜度、證明復(fù)雜度、并行計(jì)算等計(jì)算機(jī)科學(xué)基礎(chǔ)領(lǐng)域做出的基礎(chǔ)性和持久的貢獻(xiàn)，以及對基本圖形屬性理解的貢獻(xiàn)。

Avi Wigderson

在一系列研究成果中，Wigderson證明，在人們普遍認(rèn)可的計(jì)算假設(shè)下，每個(gè)概率多項(xiàng)式時(shí)間算法都可以完全去隨機(jī)化(derandomized)。換句話說，多項(xiàng)式時(shí)間計(jì)算不需要隨機(jī)性。在密碼學(xué)領(lǐng)域，Wigderson與人合著了兩篇具有里程碑意義的論文，論證了如何在不誠實(shí)的參與者面前安全地計(jì)算任何函數(shù)。他也是一個(gè)團(tuán)隊(duì)的一員，這個(gè)團(tuán)隊(duì)展示了所有短證明問題(NP中的所有問題)實(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年獲得哥德爾獎(Godel Prize)，獲獎原因是他與Omer Reingold和Salil Vadhan合作的工作，并在1994年獲得了內(nèi)萬林納獎(Nevanlinna Prize)。

Avi Wigderson還是阿里巴巴達(dá)摩院學(xué)術(shù)委員會的十位頂尖科學(xué)家之一。

高德納獎旨在表彰個(gè)人對計(jì)算機(jī)科學(xué)基礎(chǔ)的杰出貢獻(xiàn)，以及他們在該領(lǐng)域長期的整體影響。高德納獎的命名取自斯坦福大學(xué)的高德納 (Donald Knuth)，他被稱為 “算法分析之父”。該獎項(xiàng)由 ACM 算法與計(jì)算理論特別興趣組 (SIGACT) 和 IEEE 計(jì)算機(jī)學(xué)會計(jì)算數(shù)學(xué)基礎(chǔ)技術(shù)委員會 (TCMF) 聯(lián)合頒發(fā)。

哥德爾獎(G?del Prize)

2019年哥德爾獎授予以色列威茨曼研究所的Irit Dinur教授，表彰她在“The PCP Theorem by Gap Amplification”論文中證明了PCP定理。

Irit Dinur

PCP定理是計(jì)算理論中最具影響力的結(jié)果之一，對研究近似問題的固有難度和概率證明系統(tǒng)研究都具有重要的意義。Dinur的論文提供了PCP定理的另一種證明，它與原來的證明有本質(zhì)的不同。她的新證明比原來的證明簡單得多，使其在復(fù)雜性課程中的演示成為一項(xiàng)可行的任務(wù)。此外，該證明顯著改進(jìn)了所得PCP的重要參數(shù)，對本地可測試代碼產(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é)獎(2012年)和布魯諾紀(jì)念獎(2007)。

哥德爾獎表彰對數(shù)學(xué)邏輯和計(jì)算機(jī)科學(xué)基礎(chǔ)的重大貢獻(xiàn)。該獎項(xiàng)以1906年出生在奧匈帝國(現(xiàn)捷克共和國)的庫爾特·哥德爾(Kurt G?del)命名。哥德爾的工作對20世紀(jì)的科學(xué)和哲學(xué)思想產(chǎn)生了巨大的影響。哥德爾獎由ACM SIGACT和歐洲理論計(jì)算機(jī)科學(xué)協(xié)會(EATCS)聯(lián)合頒發(fā)。