クリストス・パパディミトリウ

クリストス・ハリラオス・パパディミトリウ (英語:Christos Harilaos Papadimitriou、 ギリシア語: Χρήστος Χαρίλαος Παπαδημητρίου、1949年8月16日 - )は、ギリシャ出身の理論計算機科学者、カリフォルニア大学バークレー校の計算機科学科教授である。^{[1][3][4][5][6]}

クリストス・パパディミトリウ
生誕	クリストス・ハリラオス・パパディミトリウ ギリシャ語: Χρήστος Χαρίλαος Παπαδημητρίου (1949-08-16) 1949年8月16日（75歳） アテネ
研究分野	アルゴリズム 複雑性 ゲーム理論 進化論[1]
研究機関	カリフォルニア大学バークレー校 ハーバード大学 MIT 国立アテネ工科大学 スタンフォード大学 UCSD
出身校	国立アテネ工科大学 (BS) プリンストン大学 (PhD)
博士課程 指導教員	Kenneth Steiglitz[2]
博士課程 指導学生	Esther Arkin Ziv Bar-Yossef Kamalika Chaudhuri Constantinos Daskalakis Xiaotie Deng Alex Fabrikant Deborah Goldman Paris Kanellakis Elias Koutsoupias Joseph Mitchell Alan Murray Edouard Servan-Schreiber Kunal Talwar Christopher Umans Stephen Vavasis[2]
主な受賞歴	受賞歴参照
プロジェクト:人物伝

教育

国立アテネ工科大学（英語版）に学び1972年に電気工学の学士を取得する。さらにプリンストン大学に進み、1974年に電気工学の修士号、電気工学およびコンピュータ科学科のPh.D.(博士号)を得る。

経歴

ハーバード、 MIT、 国立アテネ工科大学、 スタンフォード大学、UCSDで教鞭をとる。現在はカリフォルニア大学バークレイ校の電気工学及びコンピュータ科学科のレスター・ホーガン教授(Lester Hogan Professor)である。

2001年に ACMフェローになり、2002年にはクヌース賞を受賞した。複雑性理論、データベースの理論、組合せ最適化への貢献により米国工学アカデミー会員に選出されている。^[7] 2009年には米国科学アカデミーに選出されている。 国際会議ICALP2009ではパパディミトリウのコンピューター科学への貢献を讃えるイベントが行なわれた。^[8] 2012年には、Elias Koutsoupiasとともに無秩序の代償（英語版）の概念を導入した共同研究に対してゲーデル賞を受賞している。^[9]

パパディミトリウは 計算複雑性理論の分野で最も広く使用されている教科書の一つComputational Complexityの著者である。 他にもSanjoy Dasguptaと Umesh Vaziraniと共に教科書 Algorithms (2006)、Apostolos Doxiadisと共に劇画(graphic novel) Logicomix (2009)^[10] などを著している。

受賞歴

• 2002年 - クヌース賞
• 2004年 - IEEE Computer Society Charles Babbage Award
• 2011年 - 国立アテネ工科大学より名誉博士号^[11]
• 2012年 - ゲーデル賞
• 2013年 - スイス連邦工科大学ローザンヌ校（EPFL）より名誉博士号
• 2015年 - EATCS Award
• 2016年 - フォン・ノイマンメダル
• 2018年 - ハーヴェイ賞
• 2022年 - コンピュータパイオニア賞
• 2023年 - ジョン・フォン・ノイマン理論賞

著書・業績

• Elements of the Theory of Computation (Harry R. Lewisとの共著). Prentice-Hall, 1982; second edition September 1997.
• Combinatorial Optimization: Algorithms and Complexity (Kenneth Steiglitzとの共著). Prentice-Hall, 1982; second edition, Dover, 1998.
• The Theory of Database Concurrency Control. CS Press, 1986.
• Computational Complexity. Addison Wesley, 1994.
• Turing (a Novel about Computation). MIT Press, November 2003.
• Life Sentence to Hackers? (ギリシャ語). Kastaniotis Editions, 2004. ギリシャの新聞 To Vimaへの寄稿を編纂したもの。
• Algorithms (Sanjoy DasguptaとUmesh Vaziraniとの共著). McGraw-Hill, September 2006
• Logicomix, An Epic Search for Truth ( Apostolos Doxiadisとの共著。作画はAlecos Papadatos及びAnnie di Donnaによる。) Bloomsbury Publishing and Bloomsbury USA, September 2009.
• マイクロソフトの創設者の一人ビル・ゲイツ との共著論文がある。^[12]

私生活

2006年にカリフォルニア大学バークレー校で 教授と大学院生によるバンドLady X and The Positive Eigenvalues(レディXと正の固有値達)に参加している。^[13]

参考文献

1. クリストス・パパディミトリウの出版物 - Google Scholar
2. クリストス・パパディミトリウ - Mathematics Genealogy Project
3. クリストス・パパディミトリウ - ACM Digital Library
4. Ahmed, F (2014). “Profile of Christos Papadimitriou”. Proceedings of the National Academy of Sciences 111 (45): 15858–60. doi:10.1073/pnas.1405579111. PMC 4234580. PMID 25349396. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4234580/.
5. クリストス・パパディミトリウ - DBLP Bibliography Server
6. クリストス・パパディミトリウの出版物 - エルゼビアが提供するScopus文献データベースによる索引 (要購読契約)
7. “Member Directory at NAE Website”. 2017年7月22日閲覧。
8. “Special Events: Honoring Christos Papadimitriou Scientific Contribution to Computer Science”. ICALP 2009 – 36th International Colloquium on Automata, Languages and Programming. March 6, 2012時点のオリジナルよりアーカイブ。2009年6月9日閲覧。
9. “Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory”. (16 May 2012). http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012 16 May 2012閲覧。
10. Logicomix
11. “Live feed from the Award Ceremony of an onorary doctorate from the NTUA to the UC Berkeley Professor Chr. Papadimitriou”. 2016年3月3日時点のオリジナルよりアーカイブ。2014年6月17日閲覧。
12. Gates W.H.; Papadimitriou, C.H. Bounds for sorting by prefix reversal.
13. “Engineers rock — Out of the EECS department comes a hot new band”. May 31, 2013時点のオリジナルよりアーカイブ。2013年12月29日閲覧。

外部リンク

• Christos Papadimitriou | Columbia Engineering：本人のウェブサイト