괴델상

괴델상(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바바이 라슬로대화형 증명 시스템을 개발한 공로샤피 골드와서실비오 미카리슐로모 모란찰스 라코프1994요한 하스타드상수 깊이의 부울 회로의 크기에 대한 지수적 하한값 (패리티 함수)을 구한 공로1995닐 이머만비결정론적 공간 복잡도에 관한 임머만-셀레프세니 정리를 한 공로로베르트 셀레프세니1996마크 제럼마르코프 연쇄와 행렬의 영구적인 근사에 관한 작업을 한 공로알리스테어 신클레어1997조셉 핼펀분산 환경에서 ‘지식’에 대한 공식적인 개념을 정의한 공로.요람 모세1998토다 세이노스케PP (계산 방법)와 양화사의 교대 사이의 연관성을 정리한 공로 (토다 정리)1999피터 쇼어양자 컴퓨터에서 다항식 시간 내에 숫자를 인수분해하기 위한 쇼어 알고리즘을 정리한 공로2000모셰 바디유한 상태 기계를 이용한 시간 논리에 관한 작업한 공로피에르 볼퍼2001산지브 아로라PCP 정리와 근사화의 어려움에 대한 응용을 한 공로우리엘 파이기샤피 골드와서카르스텐 룬드바바이 라슬로라지브 모트와니슈무엘 사프라마두 수단마리오 세게디2002제르 세니제르그결정적 푸시다운 오토마타의 동등성이 결정 가능하다는 것을 증명한 공로2003요아프 프룬트기계 학습의 에이다부스트 알고리즘을 개발한 공로로버트 샤파이어2004모리스 헐리히분산 컴퓨팅 이론에 대한 토폴로지 응용 프로그램을 개발한 공로마이클 삭스니르 샤빗포티오스 자하로글루2005노가 알론스트리밍 알고리즘에 대한 기초적인 기여를 한 공로요시 마티아스마리오 세게디2006마닌드라 아그라왈AKS 소수판별법을 개발한 공로니라즈 카얄니틴 삭세나2007알렉산더 라즈보로프자연적 증명을 한 공로스티븐 루디치2008다니엘 스피엘만알고리즘의 매끄러운 분석을 한 공로텅샹화2009오머 라인골드그래프의 지그재그 곱과 로직 공간에서의 무향 연결성을 개발한 공로살릴 바단아비 위그더슨2010산지브 아로라유클리드 외판원 문제에 대한 다항시간 근사해법을 동시에 발견한 공로조셉 미첼2011요한 하스타드다양한 조합 문제에 대한 최적의 비근사성 결과를 증명한 공로2012엘리아스 쿠수피아스알고리즘 게임 이론의 기초를 마련한 공로크리스토스 파파디미트리우노암 니산아미르 로넨팀 러프가든타르도스 에바2013단 보네이다자간 디피-헬먼 키 교환 및 암호화의 보네-프랭클린 계산 방식을 고안한 공로매튜 K. 프랭클린앙투안 주2014로널드 페이긴미들웨어를 위한 최적 집계 알고리즘을 개발한 공로암논 로템모니 나오르2015다니엘 스피엘만밀접한 선형 시간 '라플라시안 솔버' 에 관한 논문들을 발표한 공로텅샹화2016스티븐 브룩스동시 분리 논리를 발명한 공로피터 오헤른2017신시아 드워크차등 개인정보 보호방법을 발명한 공로프랭크 맥셰리코비 니심애덤 D. 스미스2018오데드 레게브오류 문제를 통한 학습을 소개한 공로2019이릿 디누르갭 증폭을 통한 PCP 정리를 새롭게 증명한 공로2020로빈 모저로바스 울안 보조정리에 대한 자연적 증명을 한 공로가르보 타르도스2021안드레이 불라토프제약 충족 문제의 계산 문제 분류에 관한 연구를 한 공로차이진이첸시마틴 다이어데이비드 리처비2022즈비카 브라케르스키효율적인 완전 동형 암호 (FHE) 방식을 구축하여 암호화에 혁신적 기여를 한 공로크레이그 젠트리비노드 바이쿤타나탄2023사무엘 피오리니외판원 문제 (다면체)에 대한 모든 확장된 공식이 지수적 크기를 갖는다는 것을 증명한 공로세르주 마사르세바스티안 포쿠타한스 라지 티와리로날드 드 울프토마스 로스보스2024라이언 윌리엄스회로 범위 하한과 알고리즘 하한 패러다임을 수행한 공로

수상자들의 논문

 같이 보기 
 :en:List of computer science awards

 각주 

참고
 괴델상 수상자의 목록

분류:이론 컴퓨터 과학
분류:컴퓨터 과학상
분류:쿠르트 괴델
분류:1993년 설립