괴델상

괴델상(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

참고

• 괴델상 수상자의 목록