'''괴델상'''(Gödel Prize)은 쿠르트 괴델을 기리기 위해 만들었으며 이론 컴퓨터 과학 부문에서 특출난 논문을 발표한 사람에게 주는 상이다. 이론 컴퓨터 과학 유럽 연합(EATCS)(en)과 ACM SIGACT가 공동으로 수여한다. 이론 컴퓨터 과학에 대한 괴델과의 연관을 말하자면, 그는 1956년 노이만에게 편지를 썼는데 특정 NP-완전 문제가 제곱, 혹은 선형의 시간 내에 풀릴 있는 지에 대해 물어봤으며 그때 처음으로 P-NP 문제를 언급한 사람이었다. 괴델상은 1993년부터 수여되기 시작했다. 수여식은 STOC(컴퓨터 이론 ACM 심포지엄, 북미의 주요 이론 컴퓨터 과학 학회 하나)과 Colloquium on Automata, Languages and Programming, 유럽의 주요 이론 컴퓨터 과학 학회 하나) 군데에서 열린다. 상을 받을 자격이 되려면, (이전에는 최근 7년 이었다.) 최근 14년 내에 학술지에 게재된 논문이어야 한다. 괴델상은 5000 미국 달러를 포함하고 있다. 위원회 여섯 명이 수상자를 지목한다. EATCS 연합장과 SIGACT 연합장이 3년의 기간을 두고 각각의 위원회에서 3명씩 임명한다. EATCS와 SIGACT의 대표는 번갈아 가면서 위원회의 위원장을 맡는다. == 수상자 == 연도 이름 노트 논문 게재 연도 1993 라슬로 버버이(László Babai), 샤피 골드바서(Shafi Goldwasser), 실비오 미칼리(Silvio Micali), 슐로모 모란(Shlomo Moran), 찰스 래코프(Charles Rackoff) for the development of interactive proof systems 1988, 1989 1994 요한 호스타드(Johan Håstad) the size of constant-depth Boolean circuits (for the parity function). 1989 1995 이머만, 로베르트 셀렙체니(Róbert Szelepcsényi) for the theorem regarding space complexity 1988, 1988 1996 마크 제럼(Mark Jerrum), 앨리스터 싱클레어(Alistair Sinclair) permanent of matrix 1989, 1989 1997 조지프 핼펀(Joseph Halpern), 요람 모세스(Yoram Moses) for defining formal notion of "knowledge" in distributed environments 1990 1998 도다 세이노스케(Seinosuke Toda) PP) and alternation of quantifiers (PH (complexity)PH) 1991 1999 피터 쇼어(Peter Shor) factoring numbers in polynomial time on quantum computer 1997 2000 모셰 Y. 바르디(Moshe Y. Vardi), 피에르 월페르(Pierre Wolper) for work on temporal logic with finite automata 1994 2001 산지브 아로라(Sanjeev Arora), 우리엘 파이게(Uriel Feige), 샤피 골드바서(Shafi Goldwasser), 카르스텐 룬드(Carsten Lund), 라슬로 로바시(László Lovász), 란지브 모트와니(Rajeev Motwani), 슈무엘 사프라(Shmuel Safra), 마두 수단(Madhu Sudan), 마리오 셰게디(Mario Szegedy) for the PCP theorem and its applications to hardness of approximation 1996, 1998, 1998 2002 제로 세니제르그(Géraud Sénizergues) deterministic pushdown automata is (Decidability 2001 2003 요아브 프로인드(Yoav Freund), 로버트 셔파이어(Robert Schapire) for the AdaBoost algorithm in machine learning 1997 2004 모리스 헐리히(Maurice Herlihy), 마이클 색스(Michael Saks), 니르 샤비트(Nir Shavit), 포티오스 자하로을루(Fotios Zaharoglou) for applications of topology to the theory of distributed computing 1999, 2000 2005 노가 알론(Noga Alon), 요시 마티아스(Yossi Matias), 마리오 셰게디(Mario Szegedy) for their foundational contribution to streaming algorithms 1999 2006 마닌드라 아그라왈(Manindra Agrawal), 니라이 카얄(Neeraj Kayal), 니틴 삭세나(Nitin Saxena) for the AKS primality test 2004 2007 알렉산드르 라즈보로프(Alexander Razborov), 스티븐 루디시(Steven Rudich) for natural proofs 1997 2008 대니얼 스필먼(Daniel Spielman), 텅상화(Shanghua Teng) for smoothed analysis of algorithms 2004 2009 오메르 레인골드(Omer Reingold), 살릴 바단(Salil Vadhan), 아비 위그데르손(Avi Wigderson) graphs and connectivity) in log space 2002, 2008 2010 산지브 아로라(Sanjeev Arora), 조지프 S. B. 미첼(Joseph S. B. Mitchell) for their concurrent discovery of polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP) 1998, 1999 2011 요한 호스타드(Johan Håstad) for proving optimal result for various combinatorial problems 2001 2012 엘리아스 쿠추피아스(Elias Koutsoupias), 흐리스토스 Papadimitriou), 노암 니산(Noam Nisan), 아미르 로넨(Amir Ronen), 러프가든(Tim Roughgarden), 터르도시 에버(Éva Tardos) for laying the foundations of algorithmic game theory 2009, 2002, 2001 2013 보네이(Dan Boneh), 매슈 K. 프랭클린(Matthew K. Franklin), 앙투안 주(Antoine Joux) for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography 2003, 2004 2014 로널드 페이긴(Ronald Fagin), 암논 로템(Amnon Lotem), 모니 나오르(Moni Naor) for Optimal Aggregation Algorithms for Middleware 2003, 2015 대니얼 스필먼(Daniel Spielman), 텅상화(Shanghua Teng) for their series of papers on Laplacian solvers 2011 2013 2014 2016 스티븐 브룩스(Stephen Brookes), 피터 W. 오헌(Peter W. O'Hearn) Concurrent Separation Logic 2007, 2007 2017 신시아 드워크(Cynthia Dwork), 프랭크 맥셰리(Frank McSherry), 코비 니심(Kobbi Nissim), 애덤 D. 스미스(Adam D. Smith) for the invention of differential privacy 2006 2018 오데드 레게브(Oded Regev) for introducing the Learning with errors problem 2009 2019 이리트 디누르(Irit Dinur) for her new proof of the PCP theorem by gap amplification 2007 ==수상자들의 논문== == 같이 보기 == :en:List of computer science awards == 각주 == ==참고== 괴델상 수상자의 목록 분류:이론 컴퓨터 과학 분류:컴퓨터 과학상 분류:1993년 설립 분류:정기행사