괴델상

1. 개요

괴델상은 이론 컴퓨터 과학 분야의 뛰어난 업적을 기리기 위해 수여되는 상으로, 1993년부터 매년 수여되고 있다. 대화형 증명 시스템, 쇼어의 알고리즘, 차등 프라이버시 등 다양한 분야에서 혁신적인 연구를 수행한 학자들이 수상했으며, 수상자 목록과 수상 이유, 발표 연도에 대한 정보가 제공된다.

2. 수상자 목록

2.1. 1993년 ~ 2000년

1993년부터 2000년까지 괴델상 수상자들은 이론 전산학 분야에서 중요한 업적을 남겼다.

2.1.1. 1993년

바바이 라슬로, 샤피 골드와서, 실비오 미카리, 슐로모 모란, 찰스 라코프는 대화형 증명 시스템을 개발한 공로로 1993년 괴델상을 수상했다.

2.1.2. 1994년

요한 하스타드는 상수 깊이의 부울 회로 크기에 대한 지수적 하한값 (패리티 함수)을 구한 공로로 1994년 괴델상을 수상했다.

2.1.3. 1995년

닐 이머만과 로베르트 셀레프세니는 비결정론적 공간 복잡도에 관한 임머만-셀레프세니 정리를 증명하여 이 상을 받았다.

2.1.4. 1996년

마크 제럼과 알리스테어 신클레어는 마르코프 연쇄와 행렬의 영구적 근사에 관한 작업으로 괴델상을 받았다.

2.1.5. 1997년

조셉 핼펀과 요람 모세는 분산 환경에서 ‘지식’에 대한 공식적인 개념을 정의한 공로로 1997년 괴델상을 수상했다.

2.1.6. 1998년

토다 세이노스케는 PP (계산 방법)와 양화사의 교대 사이의 연관성을 정리한 공로(토다 정리)로 1998년 괴델상을 수상했다.

2.1.7. 1999년

피터 쇼어는 양자 컴퓨터에서 다항식 시간 내에 숫자를 인수분해하는 쇼어 알고리즘을 정리한 공로로 1999년 괴델상을 받았다.

2.1.8. 2000년

모셰 바디와 피에르 볼퍼는 유한 상태 기계를 이용한 시간 논리에 관한 연구로 2000년 괴델상을 받았다.

2.2. 2001년 ~ 2010년

2001년부터 2010년까지 괴델상은 이론 컴퓨터 과학 분야에서 중요한 업적을 남긴 학자들에게 수여되었다. 각 수상자와 주요 업적은 다음과 같다.

2.2.1. 2001년

PCP 정리와 근사화의 어려움에 대한 응용을 연구한 공로로 산지브 아로라, 우리엘 파이기, 샤피 골드와서, 카르스텐 룬드, 바바이 라슬로, 라지브 모트와니, 슈무엘 사프라, 마두 수단, 마리오 세게디가 2001년 괴델상을 수상했다.

2.2.2. 2002년

제르 세니제르그는 결정적 푸시다운 오토마타의 동등성이 결정 가능하다는 것을 증명한 공로로 2002년 괴델상을 수상했다.

2.2.3. 2003년

요아프 프룬트와 로버트 샤파이어는 에이다부스트 알고리즘을 개발한 공로로 2003년 괴델상을 수상했다.

2.2.4. 2004년

모리스 헐리히(Maurice Herlihy^영어), 마이클 삭스(Michael Saks^영어), 니르 샤빗(Nir Shavit^영어), 포티오스 자하로글루(Fotios Zaharoglou^영어)는 분산 컴퓨팅 이론에 토폴로지 응용 프로그램을 개발한 공로로 2004년 괴델상을 수상했다.

2.2.5. 2005년

노가 알론, 요시 마티아스, 마리오 세게디는 스트리밍 알고리즘에 대한 기초적인 기여를 한 공로로 2005년 괴델상을 수상했다.

2.2.6. 2006년

마닌드라 아그라왈, 니라즈 카얄, 니틴 삭세나는 AKS 소수판별법을 개발한 공로로 괴델상을 받았다.

2.2.7. 2007년

알렉산더 라즈보로프(Alexander Razborov)와 스티븐 루디치(Steven Rudich)는 자연적 증명을 한 공로로 2007년 괴델상을 수상했다.

2.2.8. 2008년

다니엘 스피엘만과 텅샹화는 알고리즘의 매끄러운 분석을 한 공로로 2008년 괴델상을 수상했다.

2.2.9. 2009년

오머 라인골드, 살릴 바단, 아비 위그더슨은 그래프의 지그재그 곱과 로직 공간에서의 무향 연결성(undirected connectivity)을 개발한 공로로 2009년 괴델상을 수상하였다.

2.2.10. 2010년

산지브 아로라와 조셉 미첼은 유클리드 외판원 문제에 대한 다항시간 근사해법을 동시에 발견한 공로로 2010년 괴델상을 수상했다.

2.3. 2011년 ~ 2024년

2011년부터 2024년까지 괴델상은 암호학, 계산 복잡도, 알고리즘 등 다양한 분야에서 중요한 업적을 남긴 연구자들에게 수여되었다. 각 수상자와 주요 업적은 아래 표와 같다.

2.3.1. 2011년

요한 하스타드는 다양한 조합 문제에 대한 최적의 비근사성 결과를 증명한 공로로 2011년 괴델상을 수상했다.

2.3.2. 2012년

엘리아스 쿠수피아스(Elias Koutsoupias^영어), 크리스토스 파파디미트리우(Christos Papadimitriou^영어), 노암 니산(Noam Nisan^영어), 아미르 로넨(Amir Ronen^영어), 팀 러프가든(Tim Roughgarden^영어), 타르도스 에바(Éva Tardos^영어)가 알고리즘 게임 이론의 기초를 마련한 공로로 수상했다.

2.3.3. 2013년

단 보네이, 매튜 K. 프랭클린, 앙투안 주는 다자간 디피-헬먼 키 교환 및 암호화의 보네-프랭클린 계산 방식을 고안한 공로로 2013년 괴델상을 수상했다.

2.3.4. 2014년

로널드 페이긴(Ronald Fagin^영어), 암논 로템(Amnon Lotem^영어), 모니 나오르(Moni Naor^영어)는 미들웨어를 위한 최적 집계 알고리즘을 개발한 공로로 2014년 괴델상을 수상했다.

2.3.5. 2015년

다니엘 스피엘만과 텅샹화는 밀접한 선형 시간 '라플라시안 솔버'에 관한 논문들을 발표한 공로로 2015년 괴델상을 받았다.

2.3.6. 2016년

스티븐 브룩스와 피터 오헤른은 동시 분리 논리를 발명한 공로로 2016년 괴델상을 수상했다.

2.3.7. 2017년

신시아 드워크, 프랭크 맥셰리, 코비 니심, 애덤 D. 스미스는 차등 개인정보 보호 방법을 발명한 공로로 2017년 괴델상을 수상했다.

2.3.8. 2018년

오데드 레게브는 오류 문제를 통한 학습을 소개한 공로로 2018년 괴델상을 수상했다.

2.3.9. 2019년

이릿 디누르는 갭 증폭을 통해 PCP 정리의 새로운 증명을 제시한 공로로 2019년 괴델상을 수상했다.

2.3.10. 2020년

Robin Moser^영어와 Gábor Tardos^영어는 로바스 울안 보조정리에 대한 자연적 증명을 한 공로로 2020년 괴델상을 수상했다.

2.3.11. 2021년

안드레이 불라토프, 차이진이, 첸시, 마틴 다이어, 데이비드 리처비는 제약 충족 문제의 계산 문제 분류에 관한 연구를 한 공로로 2021년 괴델상을 수상했다.

2.3.12. 2022년

즈비카 브라케르스키, 크레이그 젠트리, 비노드 바이쿤타나탄은 효율적인 완전 동형 암호 (FHE) 방식을 구축하여 암호화에 혁신적 기여를 한 공로로 2022년 괴델상을 수상했다.

2.3.13. 2023년

사무엘 피오리니(Samuel Fiorini), 세르주 마사르(Serge Massar), 세바스티안 포쿠타(Sebastian Pokutta), 한스 라지 티와리(Hans Raj Tiwary), 로날드 드 울프(Ronald de Wolf), 토마스 로스보스는 외판원 문제 (다면체)에 대한 모든 확장된 공식이 지수적 크기를 갖는다는 것을 증명한 공로로 수상하였다.

2.3.14. 2024년

{{lang는 회로 범위 하한과 알고리즘 하한 패러다임을 수행한 공로로 2024년 괴델상을 수상했다.

3. 수상자들의 논문