新智元報導
來源：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年高德納獎，表彰他在隨機計算、密碼學、電路複雜度、證明複雜度、並行計算等計算機科學基礎領域做出的基礎性和持久的貢獻，以及對基本圖形屬性理解的貢獻。
Avi Wigderson
在一系列研究成果中，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) 聯合頒發。
哥德爾獎(Gdel Prize)
2019年哥德爾獎授予以色列威茨曼研究所的Irit Dinur教授，表彰她在「The PCP Theorem by Gap Amplification 」論文中證明了PCP定理。
Irit Dinur
PCP定理是計算理論中最具影響力的結果之一，對研究近似問題的固有難度和概率證明系統研究都具有重要的意義。Dinur的論文提供了PCP定理的另一種證明，它與原來的證明有本質的不同。她的新證明比原來的證明簡單得多，使其在複雜性課程中的演示成為一項可行的任務。此外，該證明顯著改進了所得PCP的重要參數，對本地可測試代碼產生了相同的改進，並激發了包括實際應用在內的許多研究。為如此重要的結果提供另一種證明是一項重大成就，特別是該證明解決了許多研究人員感到困惑的問題，並解決了該領域的一個中心開放問題。
Dinur在特拉維夫大學獲得博士學位。之後，她先後在普林斯頓高等研究院、NEC和加州大學伯克利分校任職，之後加入以色列魏茨曼科學研究所擔任計算機科學教授。Dinur還獲得了Anna and Lajos Erds Prize數學獎(2012年)和布魯諾紀念獎(2007)。
哥德爾獎表彰對數學邏輯和計算機科學基礎的重大貢獻。該獎項以1906年出生在奧匈帝國(現捷克共和國)的庫爾特·哥德爾(Kurt Gdel)命名。哥德爾的工作對20世紀的科學和哲學思想產生了巨大的影響。哥德爾獎由ACM SIGACT和歐洲理論計算機科學協會(EATCS)聯合頒發。
原文：
https://www.acm.org/media-center/2019/june/sigact-knuth-goedel-prizes