2019高德納獎、哥德爾獎公布！阿里達摩院、以色列科學家獲獎

新智元報道

來源：acm.org

編輯：肖琴

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

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

高德納獎(Donald E. Knuth Prize)

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

在一系列研究成果中，Wigderson證明，在人們普遍認可的計算假設下，每個概率多項式時間演算法都可以完全去隨機化(derandomized)。換句話說，多項式時間計算不需要隨機性。在密碼學領域，Wigderson與人合著了兩篇具有里程碑意義的論文，論證了如何在不誠實的參與者面前安全地計算任何函數。他也是一個團隊的一員，這個團隊展示了所有短證明問題(NP中的所有問題)實際上都有零知識證明：即證明只產生其有效性的證據，一個中心密碼結構。

Wigderson於1983年在普林斯頓大學獲得博士學位。隨後，他在加州大學伯克利分校擔任客座助理教授，在IBM擔任訪問科學家，並在伯克利的數學科學研究所(MSRI)擔任研究員，1986年加入希伯來大學(Hebrew University)擔任教員。自1999年以來，Wigderson一直是高等研究院數學學院的教授。Wigderson還在2009年獲得哥德爾獎(Godel Prize)，獲獎原因是他與Omer Reingold和Salil Vadhan合作的工作，並在1994年獲得了內萬林納獎(Nevanlinna Prize)。

Avi Wigderson還是阿里巴巴達摩院學術委員會的十位頂尖科學家之一。

高德納獎旨在表彰個人對計算機科學基礎的傑出貢獻，以及他們在該領域長期的整體影響。高德納獎的命名是為了紀念斯坦福大學的高德納(Donald Knuth)，他被稱為「演算法分析之父」。該獎項由ACM演算法與計算理論特別興趣組(SIGACT)和IEEE計算機學會計算數學基礎技術委員會(TCMF)聯合頒發。

哥德爾獎(G?del Prize)

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

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

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

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

原文：

https://www.acm.org/media-center/2019/june/sigact-knuth-goedel-prizes

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！