괴델상
괴델상(Gödel Prize)은 쿠르트 괴델을 기리기 위해 만들었으며 이론 컴퓨터 과학 부문에서 특출난 논문을 발표한 사람에게 주는 상이다. 이론 컴퓨터 과학 유럽 연합(EATCS)(en)과 ACM SIGACT가 공동으로 수여한다. 이론 컴퓨터 과학에 대한 괴델과의 연관을 말하자면, 그는 1956년 존 폰 노이만에게 편지를 썼는데 특정 NP-완전 문제가 제곱, 혹은 선형의 시간 내에 풀릴 수 있는 지에 대해 물어봤으며 그때 처음으로 P-NP 문제를 언급한 사람이었다.[1]
괴델상은 1993년부터 수여되기 시작했다. 수여식은 STOC(컴퓨터 이론 ACM 심포지엄, 북미의 주요 이론 컴퓨터 과학 학회 중 하나)과 ICALP(en)(International Colloquium on Automata, Languages and Programming, 유럽의 주요 이론 컴퓨터 과학 학회 중 하나) 중 한 군데에서 열린다. 상을 받을 자격이 되려면, (이전에는 최근 7년 이었다.) 최근 14년 내에 학술지에 게재된 논문이어야 한다. 괴델상은 5000 미국 달러를 포함하고 있다.[2]
위원회 중 여섯 명이 수상자를 지목한다. 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 | 라이언 윌리엄스 | 회로 범위 하한과 알고리즘 하한 패러다임을 수행한 공로 |
수상자들의 논문
[편집]같이 보기
[편집]각주
[편집]- ↑ “The Gödel Letter”. 2009년 2월 12일.
- ↑ “2017 Gödel Prize”. 《European Association for Theoretical Computer Science》. EATCS. 2017년 3월 29일에 확인함.