괴델상

'''괴델상'''(Gödel Prize)은 쿠르트 괴델을 기리기 위해 만들었으며 이론 컴퓨터 과학 부문에서 특출난 논문을 발표한 사람에게 주는 상이다. 이론 컴퓨터 과학 유럽 연합(EATCS)(en)과 ACM SIGACT가 공동으로 수여한다. 이론 컴퓨터 과학에 대한 괴델과의 연관을 말하자면, 그는 1956년 존 폰 노이만에게 편지를 썼는데 특정 NP-완전 문제가 제곱, 혹은 선형의 시간 내에 풀릴 수 있는 지에 대해 물어봤으며 그때 처음으로 P-NP 문제를 언급한 사람이었다.
괴델상은 1993년부터 수여되기 시작했다. 수여식은 STOC(컴퓨터 이론 ACM 심포지엄, 북미의 주요 이론 컴퓨터 과학 학회 중 하나)과 ICALP(en)(International 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 Immerman–Szelepcsényi theorem regarding nondeterministic space complexity 
 1988, 1988
1996 
마크 제럼(Mark Jerrum), 앨리스터 싱클레어(Alistair Sinclair) 
permanent of a matrix 
 1989, 1989
1997 
조지프 핼펀(Joseph Halpern), 요람 모세스(Yoram Moses) 
 for defining a 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 a 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 (logic))decidable 
 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 USTCON(undirected connectivity) in log space 
 2002, 2008
2010 
산지브 아로라(Sanjeev Arora), 조지프 S. B. 미첼(Joseph S. B. Mitchell)
 for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP) 
 1998,
1999
2011 
 요한 호스타드(Johan Håstad) 
 for proving optimal inapproximability result for various combinatorial problems  
 2001
2012 
 엘리아스 쿠추피아스(Elias Koutsoupias), 흐리스토스 파파디미트리우(Christos 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 nearly-linear-time 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년 설립