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

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

高德納獎(Donald E. Knuth Prize)

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

Avi Wigderson

在一系列研究成果中，Wigderson證明，在人們普遍認可的計算假設(shè)下，每個概率多項式時間算法都可以完全去隨機化(derandomized)。換句話說，多項式時間計算不需要隨機性。在密碼學(xué)領(lǐng)域，Wigderson與人合著了兩篇具有里程碑意義的論文，論證了如何在不誠實的參與者面前安全地計算任何函數(shù)。他也是一個團隊的一員，這個團隊展示了所有短證明問題(NP中的所有問題)實際上都有零知識證明：即證明只產(chǎn)生其有效性的證據(jù)，一個中心密碼結(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還是阿里巴巴達摩院學(xué)術(shù)委員會的十位頂尖科學(xué)家之一。

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

哥德爾獎(G?del Prize)

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

Irit Dinur

PCP定理是計算理論中最具影響力的結(jié)果之一，對研究近似問題的固有難度和概率證明系統(tǒng)研究都具有重要的意義。Dinur的論文提供了PCP定理的另一種證明，它與原來的證明有本質(zhì)的不同。她的新證明比原來的證明簡單得多，使其在復(fù)雜性課程中的演示成為一項可行的任務(wù)。此外，該證明顯著改進了所得PCP的重要參數(shù)，對本地可測試代碼產(chǎn)生了相同的改進，并激發(fā)了包括實際應(yīng)用在內(nèi)的許多研究。為如此重要的結(jié)果提供另一種證明是一項重大成就，特別是該證明解決了許多研究人員感到困惑的問題，并解決了該領(lǐng)域的一個中心開放問題。

Dinur在特拉維夫大學(xué)獲得博士學(xué)位。之后，她先后在普林斯頓高等研究院、NEC和加州大學(xué)伯克利分校任職，之后加入以色列魏茨曼科學(xué)研究所擔(dān)任計算機科學(xué)教授。Dinur還獲得了Anna and Lajos Erd?s Prize數(shù)學(xué)獎(2012年)和布魯諾紀念獎(2007)。

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