크리스토스 파파디미트리우

1. 개요

크리스토스 파파디미트리우는 전기 공학 및 컴퓨터 과학 분야의 저명한 학자이다. 아테네 국립 공과대학교에서 학사 학위를, 프린스턴 대학교에서 석사 및 박사 학위를 취득했다. 하버드 대학교, 매사추세츠 공과대학교, 스탠퍼드 대학교 등 여러 대학에서 교수로 재직했으며, 현재 컬럼비아 대학교 컴퓨터 과학과 교수로 있다. 계산 복잡성 이론, 데이터베이스 이론, 조합 최적화 분야에 기여했으며, 빌 게이츠와 공동 연구를 수행하기도 했다. 주요 저서로는 계산 복잡성, 알고리즘, 그래픽 소설 로지코믹스 등이 있으며, 2002년 크누스 상, 2012년 괴델 상, 2016년 IEEE 존 폰 노이만 메달 등 다수의 상을 수상했다.

2. 교육

아테네 국립 공과대학교에서 전기 공학을 전공하여 1972년 학사 학위를 받았다. 이후 프린스턴 대학교 대학원에서 1974년 전기 공학 석사 학위를 취득했으며, 1976년에는 "조합 최적화 문제의 복잡성"이라는 제목의 논문으로 전기 공학 및 컴퓨터 과학 박사 학위를 받았다.

3. 경력

크리스토스 파파디미트리우는 하버드 대학교, 매사추세츠 공과대학교, 아테네 국립 공과대학교, 스탠퍼드 대학교, 캘리포니아 대학교 샌디에이고, 캘리포니아 대학교 버클리 등에서 교수로 재직했으며, 현재는 컬럼비아 대학교의 도노반 가문 컴퓨터 과학 교수이다.

그는 계산 복잡성 이론, 데이터베이스 이론, 조합 최적화 분야에 기여한 공로를 인정받아 여러 영예를 안았다. 2001년에는 컴퓨팅 기계 협회(ACM)의 회원으로 선출되었고, 2002년에는 크누스 상을 수상했으며, 같은 해 복잡성 이론, 데이터베이스 이론, 조합 최적화에 기여한 공로로 미국 국립 공학 아카데미 회원으로 선출되었다. 2009년에는 미국 국립 과학 아카데미 회원으로 선출되었다. 또한 제36회 자동 기계, 언어 및 프로그래밍에 관한 국제 콜로키움(ICALP 2009)에서는 그의 컴퓨터 과학 분야 기여를 기념하는 특별 행사가 열렸다.

파파디미트리우는 계산 복잡성 이론 분야에서 널리 사용되는 교과서 Computational Complexity의 저자이다. 또한 산조이 다스굽타(Sanjoy Dasgupta), 우메쉬 바지라니(Umesh Vazirani)와 함께 교과서 Algorithms(2008)를, 아포스톨로스 독시아디스(Apostolos Doxiadis)와 함께 그래픽 소설 로지코믹스(2009)를 공동 저술했다.

3.1. 빌 게이츠와의 공동 연구

파파디미트리우는 하버드 대학교 학부생 시절의 빌 게이츠와 함께 팬케이크 정렬에 관한 논문을 공동으로 저술했다. 당시 빌 게이츠는 마이크로소프트를 설립하기 전이었다.

파파디미트리우는 이와 관련하여 다음과 같은 일화를 회상했다. "2년 후, 나는 그에게 우리 논문이 훌륭한 수학 저널에 게재되었다고 말하려고 전화했다. 그는 전혀 관심이 없는 것 같았다. 그는 마이크로프로세서용 코드를 작성하는 작은 회사를 운영하기 위해 뉴멕시코 주 앨버커키로 이사 갔었다. 나는 '저렇게 훌륭한 아이가. 낭비네.'"라고 말했다. 빌 게이츠가 설립한 작은 회사가 바로 마이크로소프트였다.

3.2. 내쉬 균형 계산 복잡성 연구와 칼라이 상 수상

파파디미트리우는 제자 콘스탄티노스 다스칼라키스와 폴 W. 골드버그(Paul W. Goldberg)와 함께 "The Complexity of Computing a Nash Equilibrium^영어"라는 제목의 논문을 공동으로 저술했다. 이 연구는 내쉬 균형 계산의 복잡성을 다룬 것으로, 게임 이론과 컴퓨터 과학의 융합 분야에서 중요한 기여로 평가받았다. 이 공로를 인정받아 2008년 게임 이론 학회(Game Theory Society)로부터 칼라이 상(Kalai Prize)을 수상했다. 칼라이 상은 해당 논문이 "게임 이론과 컴퓨터 과학의 융합 분야에서 최고의 논문"이며, 특히 "주요 개념적 및 기술적 기여"를 했다는 점을 근거로 수여되었다. 또한 이 논문은 산업 및 응용 수학 학회(SIAM)로부터 우수 논문상(Outstanding Paper Prize)을 받기도 했다.

3.3. 무정부 상태 가격 연구와 괴델 상 수상

2012년, 그는 엘리아스 코우트수피아스와 함께 무정부 상태의 대가 Price of anarchy^영어 개념에 대한 공동 연구로 괴델 상을 수상했다.

4. 수상 및 영예

1997년, ETH 취리히에서 명예 박사 학위를 받았다. 2011년에는 아테네 국립 공과대학교에서, 2013년에는 로잔 연방 공과대학교(EPFL)에서 명예 박사 학위를 받았다.

주요 수상 내역은 다음과 같다.

5. 저서 목록

* 계산 이론의 요소 (Elements of the theory of computation^영어). (해리 R. 루이스 공저). 프렌티스 홀, 1982년; 2판 1997년 9월.
* 조합 최적화: 알고리즘과 복잡성 (Combinatorial optimization: algorithms and complexity^영어). (케네스 스타이글리츠 공저). 프렌티스 홀, 1982년; 2판, 도버, 1998년.
* 데이터베이스 동시성 제어 이론 (The theory of database concurrency control^영어). CS 프레스, 1986년.
* 계산 복잡성 (Computational Complexity^영어). 애디슨 웨슬리, 1994년.
* 튜링 (계산에 관한 소설) (Turing (a novel about computation)^영어). MIT Press, 2003년 11월.
* 해커에게 종신형? (Isbanki gia Hacker?^ell). 카스타니오티스 에디션, 2004년. 그리스 신문 토 비마에 기고한 기사 모음.
* 알고리즘 (Introduction to Algorithms^영어). (산조이 다스굽타, 우메시 바지라니 공저). 맥그로힐, 2006년 9월.
* 로지코믹스, 진실을 향한 장대한 탐구 (Logicomix, An Epic Search for Truth^영어). (아포스톨로스 독시아디스 공저, 알레코스 파파다토스와 애니 디 돈나 그림). 블룸스버리 출판, 2009년 9월.
* 마이크로소프트 공동 창업자인 빌 게이츠와 팬케이크 정렬에 관한 논문을 공동 집필했다.

6. 기타 활동

2006년, 캘리포니아 대학교 버클리에서 교수와 대학원생으로 구성된 밴드 Lady X and The Positive Eigenvalues^영어에 참여했다.