맨위로가기

괴델상

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

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

더 읽어볼만한 페이지

  • 쿠르트 괴델 - 괴델, 에셔, 바흐
    더글러스 호프스태터의 책 "괴델, 에셔, 바흐"는 괴델의 불완전성 정리, 에셔의 미술, 바흐의 음악을 통해 재귀, 자기 참조, 지능과 의식의 본질을 탐구하며, 다양한 분야를 넘나드는 사유를 제공하여 퓰리처상을 수상하는 등 큰 반향을 일으켰다.
  • 컴퓨터 과학상 - 튜링상
    튜링상은 컴퓨터 과학 분야에 큰 공헌을 한 인물에게 수여되는 상으로, 알고리즘, 프로그래밍 언어, 인공지능 등 다양한 분야에서 혁신적인 업적을 이룬 연구자들에게 수여되며 "컴퓨터 과학 분야의 노벨상"으로 불린다.
  • 컴퓨터 과학상 - SIGCOMM상
  • 이론 컴퓨터 과학 - 알고리즘
    알고리즘은 문제 해결을 위한 명확하고 순서화된 유한 개의 규칙 집합으로, 알콰리즈미의 이름에서 유래되었으며, 수학 문제 해결 절차로 사용되다가 컴퓨터 과학에서 중요한 역할을 하며 다양한 방식으로 표현되고 효율성 분석을 통해 평가된다.
  • 이론 컴퓨터 과학 - 자동화된 추론
    자동화된 추론은 컴퓨터 프로그램을 사용하여 논리적 추론을 수행하는 인공지능 분야로, 수리 논리학의 발전과 초기 연구를 통해 자동 정리 증명 분야의 기틀을 마련했으며, AI 겨울을 겪었지만 소프트웨어 검증 등 다양한 분야에 활용되며 Coq, HOL Light 등의 증명 보조기가 개발되어 난제들의 형식적 증명에 기여했다.
괴델상
기본 정보
수여 기관이론 컴퓨터 과학 유럽 협회(EATCS) 및 컴퓨터 기계 협회(ACM)
분야이론 컴퓨터 과학
첫 시상1993년
웹사이트공식 웹사이트
명칭 유래
이름쿠르트 괴델
수상
상금$5,000

2. 수상자 목록

괴델상 수상자 목록
연도수상자수상 이유논문 발표 연도
1993바바이 라슬로, 샤피 골드와서, 실비오 미칼리, 슐로모 모란, 찰스 라코프대화형 증명 시스템 발명1988,[64] 1989[65]
1994요한 하스타드패리티 함수의 상수 깊이 회로는 크기 하한이 지수 함수가 됨1989[66]
1995닐 이머만, 로베르트 셀레프체니이머만-셀레프체니 정리1988,[67] 1988[68]
1996마크 제럼, 알리스테어 싱클레어마르코프 연쇄와 행렬의 퍼머넌트 근사에 대한 업적1989,[69] 1989[70]
1997조셉 할펀, 요람 모세스분산 환경에서 "지식"의 형식적 개념 정의1990[71]
1998토다 세이노스케토다의 정리1991[72]
1999피터 쇼어쇼어의 알고리즘1997[73]
2000모셰 바르디, 피에르 볼퍼유한 오토마타를 이용한 시상 논리에 대한 업적1994[74]
2001산지브 아로라, 우리엘 파이게, 샤피 골드와서, 카르스텐 룬드, 러슬로 러바스, 라지브 모트와니, 슈무엘 사프라, 마두 수단, 마리오 세게디PCP 정리와 근사 어려움에의 응용1996,[75] 1998,[76] 1998[77]
2002제라드 세니제르그결정적 푸시다운 오토마타의 등가성이 결정 가능함을 증명2001[78]
2003요아브 프로인트, 로버트 샤피르AdaBoost1997[79]
2004모리스 헐리히, 마이클 삭스, 니르 샤비트, 포티오스 자하로글루위상 수학의 분산 컴퓨팅에의 응용1999,[80] 2000[81]
2005노가 알론, 요시 마티아스, 마리오 세게디스트리밍 알고리즘에 대한 기본적인 기여1999[82]
2006마닌드라 아가르왈, 니라즈 카얄, 니틴 삭세나AKS 소수성 검사2004[83]
2007알렉산더 라즈보로프, 스티븐 루디치자연 증명1997[84]
2008다니엘 스필먼, 샹화 텅알고리즘의 평활화 분석2004[85]
2009오머 레인골드, 살릴 바드한, 아비 비그더슨그래프 이론에서 지그재그 곱 및 USTCON이 대수 영역에서 풀릴 수 있음2002,[86] 2008[87]
2010산지브 아로라, 조셉 S. B. 미첼유클리드 거리에 기초한 외판원 문제에 대한 다항 시간 근사 알고리즘 발견1998,[88] 1999[89]
2011요한 하스타드다양한 조합 문제에 대한 근사 불가능성 증명2001[90]
2012엘리아스 코우트소우피아스, 크리스토스 파파디미트리우, 노암 니산, 아미르 로넨, 팀 러프가든, 에바 타르도스알고리즘적 게임 이론의 기초를 세움2009,[92] 2002,[93] 2001,[94]
2013댄 본, 매튜 K. 프랭클린, 앙투안 주멀티 파티 디피-헬만 키 공유 및 본-프랭클린 방식2003,[96] 2004[97]
2014로널드 페이긴, 아므논 로템, 모니 나르미들웨어를 위한 최적의 집계 알고리즘2003,[99]
2015다니엘 스필먼, 샹화 텅거의 선형 시간의 라플라시안 솔버에 관한 일련의 논문2011,[101] 2013,[102] 2014[103]
2016스티븐 브룩스, 피터 오헌Concurrent Separation Logic 발명2007,[104] 2007[105]
2017신시아 드워크, 프랭크 맥셰리, 코비 니심, 아담 D. 스미스차등 프라이버시 발명2006[107]
2018오데드 레게브오류를 통한 학습 문제 도입2009[109]
2019이리트 디누르PCP 정리에 대한 새로운 증명2007[111]
2020로빈 모저, 가보 타르도스Lovász Local Lemma에 대한 구성적 증명2010[113]
2021 |
2022 |
2023 |
2024 |


2. 1. 1993년 ~ 2000년

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

연도수상자업적
1993바바이 라슬로, 샤피 골드와서, 실비오 미카리, 슐로모 모란, 찰스 라코프대화형 증명 시스템 개발[2][3]
1994요한 하스타드상수 깊이의 부울 회로 크기에 대한 지수적 하한값 (패리티 함수) 증명[4]
1995닐 이머만, 로베르트 셀레프세니임머만-셀레프세니 정리 증명[5][6]
1996마크 제럼, 알리스테어 신클레어마르코프 연쇄와 행렬의 영구적 근사에 관한 작업[7][8]
1997조셉 핼펀, 요람 모세분산 환경에서 ‘지식’에 대한 공식적인 개념 정의[9]
1998토다 세이노스케PP (계산 방법)와 양화사의 교대 사이의 연관성을 정리 (토다 정리)[10]
1999피터 쇼어양자 컴퓨터에서 다항식 시간 내에 숫자를 인수분해하는 쇼어 알고리즘 개발[11]
2000모셰 바디, 피에르 볼퍼유한 상태 기계를 이용한 시간 논리에 관한 연구[12]


2. 1. 1. 1993년

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

2. 1. 2. 1994년

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

2. 1. 3. 1995년

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

2. 1. 4. 1996년

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

2. 1. 5. 1997년

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

2. 1. 6. 1998년

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

2. 1. 7. 1999년

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

2. 1. 8. 2000년

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

2. 2. 2001년 ~ 2010년

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

2001년 ~ 2010년 괴델상 수상자 및 업적
연도수상자업적
2001산지브 아로라, 우리엘 파이기, 샤피 골드와서, 카르스텐 룬드, 바바이 라슬로, 라지브 모트와니, 슈무엘 사프라, 마두 수단, 마리오 세게디PCP 정리와 근사화의 어려움에 대한 응용[75][76][77]
2002제르 세니제르그결정적 푸시다운 오토마타의 동등성이 결정 가능하다는 것을 증명[78]
2003요아프 프룬트, 로버트 샤파이어기계 학습의 에이다부스트 알고리즘 개발[79]
2004모리스 헐리히, 마이클 삭스, 니르 샤빗, 포티오스 자하로글루분산 컴퓨팅 이론에 대한 토폴로지 응용 프로그램 개발[80][81]
2005노가 알론, 요시 마티아스, 마리오 세게디스트리밍 알고리즘에 대한 기초적인 기여[82]
2006마닌드라 아그라왈, 니라즈 카얄, 니틴 삭세나AKS 소수판별법 개발[83]
2007알렉산더 라즈보로프, 스티븐 루디치자연적 증명[84]
2008다니엘 스피엘만, 텅샹화알고리즘의 매끄러운 분석[85]
2009오머 라인골드, 살릴 바단, 아비 위그더슨그래프의 지그재그 곱과 로직 공간에서의 무향 연결성 개발[86][87]
2010산지브 아로라, 조셉 미첼유클리드 외판원 문제에 대한 다항시간 근사해법 동시 발견[88][89]


2. 2. 1. 2001년

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

2. 2. 2. 2002년

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

2. 2. 3. 2003년

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

2. 2. 4. 2004년

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

2. 2. 5. 2005년

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

2. 2. 6. 2006년

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

2. 2. 7. 2007년

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

2. 2. 8. 2008년

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

2. 2. 9. 2009년

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

2. 2. 10. 2010년

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

2. 3. 2011년 ~ 2024년

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

2011년 ~ 2024년 괴델상 수상자 및 업적
연도수상자업적
2011요한 하스타드다양한 조합 문제에 대한 최적의 비근사성 결과 증명[90]
2012엘리아스 쿠수피아스, 크리스토스 파파디미트리우, 노암 니산, 아미르 로넨, 팀 러프가든, 타르도스 에바알고리즘 게임 이론의 기초 마련[91]
2013단 보네이, 매튜 K. 프랭클린, 앙투안 주다자간 디피-헬먼 키 교환 및 암호화의 보네-프랭클린 계산 방식 고안[96]
2014로널드 페이긴, 암논 로템, 모니 나오르미들웨어를 위한 최적 집계 알고리즘 개발[98]
2015다니엘 스피엘만, 텅샹화밀접한 선형 시간 라플라시안 솔버에 관한 논문 발표[100]
2016스티븐 브룩스, 피터 오헤른동시 분리 논리 발명[104]
2017신시아 드워크, 프랭크 맥셰리, 코비 니심, 애덤 D. 스미스차등 개인정보 보호 방법 발명[107]
2018오데드 레게브오류 문제를 통한 학습 소개[109]
2019이릿 디누르갭 증폭을 통한 PCP 정리 증명[111]
2020로빈 모저, 가르보 타르도스로바스 울안 보조정리에 대한 자연적 증명[113]
2021안드레이 불라토프, 차이진이, 첸시, 마틴 다이어, 데이비드 리처비제약 충족 문제의 계산 문제 분류에 관한 연구[114]
2022즈비카 브라케르스키, 크레이그 젠트리, 비노드 바이쿤타나탄효율적인 완전 동형 암호 (FHE) 방식 구축[118]
2023사무엘 피오리니, 세르주 마사르, 세바스티안 포쿠타, 한스 라지 티와리, 로널드 드 울프, 토마스 로스보스외판원 문제 (다면체)에 대한 모든 확장된 공식이 지수적 크기를 갖는다는 것을 증명
2024라이언 윌리엄스회로 범위 하한과 알고리즘 하한 패러다임을 수행


2. 3. 1. 2011년

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

2. 3. 2. 2012년

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

2. 3. 3. 2013년

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

2. 3. 4. 2014년

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

2. 3. 5. 2015년

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

2. 3. 6. 2016년

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

2. 3. 7. 2017년

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

2. 3. 8. 2018년

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

2. 3. 9. 2019년

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

2. 3. 10. 2020년

Robin Moser|로빈 모저영어와 Gábor Tardos|가르보 타르도스영어는 로바스 울안 보조정리에 대한 자연적 증명을 한 공로로 2020년 괴델상을 수상했다.[38]

2. 3. 11. 2021년

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

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년

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

3. 수상자들의 논문

연도수상자수상 이유논문 발표 연도
1993라즐로 바바이, 샤피 골드와서, 실비오 미칼리, 셜로모 모란, 찰스 랙오프대화형 증명 시스템 발명1988,[64] 1989[65]
1994요한 하스타드패리티 함수의 상수 깊이 회로는 크기 하한이 지수 함수가 됨1989[66]
1995닐 이머만, 로버트 세레페체니이머만-세레페체니 정리1988,[67] 1988[68]
1996마크 제럼, 알리스테어 싱클레어마르코프 연쇄와 행렬의 퍼머넌트 근사에 대한 업적1989,[69] 1989[70]
1997조셉 할펀, 요람 모세스분산 환경에서 "지식"의 형식적 개념 정의1990[71]
1998토다 세이노스케토다의 정리1991[72]
1999피터 쇼어쇼어의 알고리즘1997[73]
2000모셰 바르디, 피에르 울퍼유한 오토마타를 이용한 시상 논리에 대한 업적1994[74]
2001산지브 아로라, 우리엘 페이게, 샤피 골드와서, 카르스텐 룬드, 러슬로 러버스, 라지브 모트와니, 슈무엘 사프라, 마두 수단, 마리오 세게디PCP 정리와 근사 어려움에의 응용1996,[75] 1998,[76] 1998[77]
2002제라드 세니제르그결정적 푸시다운 오토마타의 등가성이 결정 가능함을 증명2001[78]
2003요아브 프로인트, 로버트 샤피르AdaBoost1997[79]
2004모리스 헐리히, 마이클 삭스, 니르 샤비트, 포티오스 자하로글루위상 수학의 분산 컴퓨팅에의 응용1999,[80] 2000[81]
2005노가 알론, 요시 매티어스, 마리오 세게디스트리밍 알고리즘에 대한 기본적인 기여1999[82]
2006마닌드라 아가르왈, 니라즈 카얄, 니틴 삭세나AKS 소수성 검사2004[83]
2007알렉산더 라즈보로프, 스티븐 루디치자연 증명1997[84]
2008다니엘 스필먼, 샹화 텅알고리즘의 평활화 분석2004[85]
2009오머 레인골드, 사릴 바드한, 아비 비그더슨그래프 이론에서 지그재그 곱 및 USTCON이 대수 영역에서 풀릴 수 있음2002,[86] 2008[87]
2010산지브 아로라, 조셉 S. B. 미첼유클리드 거리에 기초한 외판원 문제에 대한 다항 시간 근사 알고리즘 발견1998,[88] 1999[89]
2011요한 하스타드다양한 조합 문제에 대한 근사 불가능성 증명2001[90]
2012엘리아스 코우트소우피아스, 크리스토스 파파디미트리우, 노암 니산, 아미르 로넨, 팀 러프가든, 에바 타르도스알고리즘적 게임 이론의 기초를 세움[91]2009,[92] 2002,[93] 2001[94]
2013댄 본, 매튜 K. 프랭클린, 앙투안 주멀티 파티 디피-헬만 키 공유 및 본-프랭클린 방식[95]2003,[96] 2004[97]
2014로널드 페이긴, 아므논 로템, 모니 나르미들웨어를 위한 최적의 집계 알고리즘[98]2003,[99]
2015다니엘 스필먼, 샹화 텅거의 선형 시간의 라플라시안 솔버에 관한 일련의 논문[100]2011[101], 2013[102], 2014[103]
2016스티븐 브룩스, 피터 오헌Concurrent Separation Logic 발명2007[104], 2007[105]
2017신시아 드워크, 프랭크 맥셰리, 코비 니심, 아담 D. 스미스차등 프라이버시 발명2006[107]
2018오데드 레게브오류를 통한 학습 문제 도입2009[109]
2019이리트 디누르PCP 정리에 대한 새로운 증명2007[111]
2020로빈 모저, 가보 타르도스Lovász Local Lemma에 대한 구성적 증명2010[113]
2021안드레이 불라토프, 진-이 차이, 시 첸, 마틴 다이어, 데이비드 리처비제약 충족 문제의 계산 복잡도 분류에 관한 연구2013,[115] 2013[116] 2017[117]
2022즈비카 브라커스키, 크레이그 젠트리, 비노드 바이쿤타나탄효율적인 완전 동형 암호 구축을 통한 암호 이론에 대한 혁신적인 기여2014,[119] 2014[120]
2023사무엘 피오리니, 세르주 마사르, 세바스티안 포쿠타, 한스 라지 티와리, 로널드 드 울프  
2024라이언 윌리엄스  


참조

[1] 웹사이트 The Gödel Letter https://rjlipton.wor[...] 2009-02-12
[2] 논문 Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class http://crypto.cs.mcg[...]
[3] 논문 The knowledge complexity of interactive proof systems http://crypto.cs.mcg[...]
[4] 서적 Randomness and Computation JAI Press
[5] 논문 Nondeterministic space is closed under complementation http://www.cs.umass.[...]
[6] 논문 The method of forced enumeration for nondeterministic automata http://dml.cz/bitstr[...]
[7] 논문 Approximate counting, uniform generation and rapidly mixing Markov chains
[8] 논문 Approximating the permanent
[9] 논문 Knowledge and common knowledge in a distributed environment https://www.cs.corne[...]
[10] 논문 PP is as hard as the polynomial-time hierarchy http://faculty.cs.ta[...] 2010-06-08
[11] 논문 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
[12] 논문 Reasoning about infinite computations http://reference.kfu[...]
[13] 논문 Interactive proofs and the hardness of approximating cliques http://groups.csail.[...]
[14] 논문 Probabilistic checking of proofs: a new characterization of NP http://www.cs.umd.ed[...]
[15] 논문 Proof verification and the hardness of approximation problems https://www.cs.umd.e[...]
[16] 논문 L(A) = L(B)? decidability results from complete formal systems
[17] 논문 A decision-theoretic generalization of on-line learning and an application to boosting http://www-ai.cs.tu-[...]
[18] 논문 The topological structure of asynchronous computability http://www.cs.brown.[...]
[19] 논문 Wait-free k-set agreement is impossible: The topology of public knowledge
[20] 논문 The space complexity of approximating the frequency moments http://www.math.tau.[...]
[21] 논문 PRIMES is in P
[22] 논문 Natural proofs
[23] 논문 Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
[24] 논문 Entropy waves, the zig-zag graph product, and new constant-degree expanders
[25] 논문 Undirected connectivity in log-space http://www.weizmann.[...]
[26] 논문 Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
[27] 논문 Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
[28] 논문 Some optimal inapproximability results http://www.csc.kth.s[...]
[29] 뉴스 Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory http://www.acm.org/p[...] 2012-05-16
[30] 간행물 Worst-case equilibria
[31] 간행물 How bad is selfish routing?
[32] 간행물 Algorithmic Mechanism Design
[33] 웹사이트 ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security http://www.acm.org/p[...] 2013-06-01
[34] 간행물 Identity-based encryption from the Weil pairing
[35] 간행물 A one round protocol for tripartite Diffie-Hellman
[36] 간행물 Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources https://eatcs.org/in[...] Association for Computing Machinery 2014-04-30
[37] 논문 Optimal aggregation algorithms for middleware
[38] 웹사이트 2015 Gödel Prize announcement http://www.sigact.or[...] 2017-12-09
[39] 논문 Spectral Sparsification of Graphs
[40] 논문 A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
[41] 논문 Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
[42] 논문 A Semantics for Concurrent Separation Logic https://www.cs.cmu.e[...] 2007
[43] 논문 Resources, Concurrency and Local Reasoning http://www.cs.ucl.ac[...] 2007
[44] 웹사이트 2017 Gödel Prize https://www.eatcs.or[...] EATCS 2017-03-29
[45] conference Calibrating Noise to Sensitivity in Private Data Analysis Springer-Verlag
[46] 웹사이트 2018 Gödel Prize citation http://eatcs.org/ind[...]
[47] 논문 On lattices, learning with errors, random linear codes, and cryptography
[48] 웹사이트 2019 Gödel Prize citation http://eatcs.org/ind[...]
[49] 논문 The PCP theorem by gap amplification https://dl.acm.org/c[...]
[50] 웹사이트 2020 Gödel Prize citation http://eatcs.org/ind[...]
[51] 논문 A constructive proof of the general Lovász Local Lemma
[52] 웹사이트 2021 Gödel Prize citation https://eatcs.org/in[...]
[53] 논문 The complexity of the counting constraint satisfaction problem Association for Computing Machinery
[54] 논문 An Effective Dichotomy for the Counting Constraint Satisfaction Problem Society for Industrial & Applied Mathematics (SIAM)
[55] 논문 Complexity of Counting CSP with Complex Weights Association for Computing Machinery 2017-06-22
[56] 웹사이트 2022 Gödel Prize citation https://eatcs.org/in[...]
[57] 논문 Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$ http://dx.doi.org/10[...] 2014-01
[58] 서적 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference ACM Press 2012
[59] 웹사이트 2023 Gödel Prize citation https://eatcs.org/in[...]
[60] 논문 Exponential Lower Bounds for Polytopes in Combinatorial Optimization https://doi.org/10.1[...] 2015
[61] 논문 The Matching Polytope has Exponential Extension Complexity https://doi.org/10.1[...] 2017
[62] 웹사이트 2024 Gödel Prize citation https://eatcs.org/in[...]
[63] 서적 2011 IEEE 26th Annual Conference on Computational Complexity IEEE 2011-06
[64] 간행물 Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class http://crypto.cs.mcg[...]
[65] 간행물 The knowledge complexity of interactive proof systems http://crypto.cs.mcg[...]
[66] 간행물 Randomness and Computation JAI Press
[67] 간행물 Nondeterministic space is closed under complementation http://www.cs.umass.[...]
[68] 간행물 The method of forced enumeration for nondeterministic automata http://dml.cz/bitstr[...]
[69] 간행물 Approximate counting, uniform generation and rapidly mixing Markov chains
[70] 간행물 Approximating the permanent
[71] 논문 Knowledge and common knowledge in a distributed environment https://www.cs.corne[...]
[72] 논문 PP is as hard as the polynomial-time hierarchy http://faculty.cs.ta[...]
[73] 논문 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
[74] 논문 Reasoning about infinite computations https://doi.org/10.1[...]
[75] 논문 Interactive proofs and the hardness of approximating cliques http://groups.csail.[...]
[76] 논문 Probabilistic checking of proofs: a new characterization of NP https://doi.org/10.1[...]
[77] 논문 Proof verification and the hardness of approximation problems https://doi.org/10.1[...]
[78] 논문 L(A) = L(B)? decidability results from complete formal systems
[79] 논문 A decision-theoretic generalization of on-line learning and an application to boosting http://www-ai.cs.tu-[...]
[80] 논문 The topological structure of asynchronous computability http://www.cs.brown.[...]
[81] 논문 Wait-free ''k''-set agreement is impossible: The topology of public knowledge
[82] 논문 The space complexity of approximating the frequency moments http://www.math.tau.[...]
[83] 논문 PRIMES is in P https://doi.org/10.4[...]
[84] 논문 Natural proofs
[85] 논문 Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
[86] 논문 Entropy waves, the zig-zag graph product, and new constant-degree expanders
[87] 논문 Undirected connectivity in log-space
[88] 논문 Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
[89] 논문 Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
[90] 논문 Some optimal inapproximability results http://www.nada.kth.[...]
[91] 뉴스 Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory http://www.acm.org/p[...] 2012-05-16
[92] 간행물 Worst-case equilibria
[93] 간행물 How bad is selfish routing?
[94] 간행물 Algorithmic Mechanism Design
[95] 웹사이트 ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security http://www.acm.org/p[...] 2013-06-01
[96] 간행물 Identity-based encryption from the Weil pairing
[97] 간행물 A one round protocol for tripartite Diffie-Hellman
[98] 웹사이트 Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources https://eatcs.org/in[...] 2014-04-30
[99] 간행물 Optimal aggregation algorithms for middleware
[100] 웹사이트 2015 Gödel Prize announcement http://www.sigact.or[...] 2017-12-09
[101] 간행물 Spectral Sparsification of Graphs
[102] 간행물 A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
[103] 간행물 Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
[104] 간행물 A Semantics for Concurrent Separation Logic https://www.cs.cmu.e[...] 2007
[105] 간행물 Resources, Concurrency and Local Reasoning http://www.cs.ucl.ac[...] 2007
[106] 웹사이트 2017 Gödel Prize https://www.eatcs.or[...] EATCS 2017-03-29
[107] 간행물 Calibrating Noise to Sensitivity in Private Data Analysis Springer-Verlag
[108] 웹사이트 2018 Gödel Prize citation http://eatcs.org/ind[...] 2020-09-05
[109] 논문 On lattices, learning with errors, random linear codes, and cryptography
[110] 웹사이트 2019 Gödel Prize citation http://eatcs.org/ind[...] 2020-09-05
[111] 논문 The PCP theorem by gap amplification https://dl.acm.org/c[...]
[112] 웹사이트 2020 Gödel Prize citation http://eatcs.org/ind[...] 2020-09-05
[113] 논문 A constructive proof of the general Lovász Local Lemma
[114] 웹사이트 2021 Gödel Prize citation https://eatcs.org/in[...] 2022-08-14
[115] 논문 The complexity of the counting constraint satisfaction problem Association for Computing Machinery (ACM)
[116] 논문 An Effective Dichotomy for the Counting Constraint Satisfaction Problem Society for Industrial & Applied Mathematics (SIAM)
[117] 논문 Complexity of Counting CSP with Complex Weights Association for Computing Machinery (ACM) 2017-06-22
[118] 웹사이트 2022 Gödel Prize citation https://eatcs.org/in[...] 2022-08-14
[119] 논문 Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$ https://doi.org/10.1[...] 2014-01
[120] 논문 (Leveled) fully homomorphic encryption without bootstrapping https://doi.org/10.1[...] ACM Press 2012
[121] 웹인용 The Gödel Letter https://rjlipton.wor[...] 2009-02-12
[122] 웹인용 2017 Gödel Prize https://www.eatcs.or[...] EATCS 2017-03-29


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com