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

ACM算法與計(jì)算理論興趣組(SIGACT)今天宣布，2019年高德納獎(jiǎng)授予普林斯頓大學(xué)高等研究院教授Avi Wigderson，哥德?tīng)柂?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)。換句話說(shuō)，多項(xiàng)式時(shí)間計(jì)算不需要隨機(jī)性。在密碼學(xué)領(lǐng)域，Wigderson與人合著了兩篇具有里程碑意義的論文，論證了如何在不誠(chéng)實(shí)的參與者面前安全地計(jì)算任何函數(shù)。他也是一個(gè)團(tuán)隊(duì)的一員，這個(gè)團(tuán)隊(duì)展示了所有短證明問(wèn)題(NP中的所有問(wèn)題)實(shí)際上都有零知識(shí)證明：即證明只產(chǎn)生其有效性的證據(jù)，一個(gè)中心密碼結(jié)構(gòu)。

Wigderson于1983年在普林斯頓大學(xué)獲得博士學(xué)位。隨后，他在加州大學(xué)伯克利分校擔(dān)任客座助理教授，在IBM擔(dān)任訪問(wèn)科學(xué)家，并在伯克利的數(shù)學(xué)科學(xué)研究所(MSRI)擔(dān)任研究員，1986年加入希伯來(lái)大學(xué)(Hebrew University)擔(dān)任教員。自1999年以來(lái)，Wigderson一直是高等研究院數(shù)學(xué)學(xué)院的教授。Wigderson還在2009年獲得哥德?tīng)柂?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)，他被稱(chēng)為 “算法分析之父”。該獎(jiǎng)項(xiàng)由 ACM 算法與計(jì)算理論特別興趣組 (SIGACT) 和 IEEE 計(jì)算機(jī)學(xué)會(huì)計(jì)算數(shù)學(xué)基礎(chǔ)技術(shù)委員會(huì) (TCMF) 聯(lián)合頒發(fā)。

哥德?tīng)柂?jiǎng)(G?del Prize)

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

Irit Dinur

PCP定理是計(jì)算理論中最具影響力的結(jié)果之一，對(duì)研究近似問(wèn)題的固有難度和概率證明系統(tǒng)研究都具有重要的意義。Dinur的論文提供了PCP定理的另一種證明，它與原來(lái)的證明有本質(zhì)的不同。她的新證明比原來(lái)的證明簡(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)重大成就，特別是該證明解決了許多研究人員感到困惑的問(wèn)題，并解決了該領(lǐng)域的一個(gè)中心開(kāi)放問(wèn)題。

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)。

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