クリストス・ハリラオス・パパディミトリウ (英語:Christos Harilaos Papadimitriou、 ギリシア語: Χρήστος Χαρίλαος Παπαδημητρίου、1949年8月16日 - )は、ギリシャ出身の理論計算機科学者、カリフォルニア大学バークレー校の計算機科学科教授である。
教育 に学び1972年に電気工学の学士を取得する。さらにプリンストン大学に進み、1974年に電気工学の修士号、電気工学およびコンピュータ科学科のPh.D.(博士号)を得る。
経歴 ハーバード、 MIT、 国立アテネ工科大学、 スタンフォード大学、UCSDで教鞭をとる。現在はカリフォルニア大学バークレイ校の電気工学及びコンピュータ科学科のレスター・ホーガン教授(Lester Hogan Professor)である。
2001年に ACMフェローになり、2002年にはクヌース賞を受賞した。複雑性理論、データベースの理論、組合せ最適化への貢献により米国工学アカデミー会員に選出されている。 2009年には米国科学アカデミーに選出されている。 国際会議ICALP2009ではパパディミトリウのコンピューター科学への貢献を讃えるイベントが行なわれた。 2012年には、Elias Koutsoupiasとともにの概念を導入した共同研究に対してゲーデル賞を受賞している。
パパディミトリウは 計算複雑性理論の分野で最も広く使用されている教科書の一つComputational Complexityの著者である。 他にもSanjoy Dasguptaと Umesh Vaziraniと共に教科書 Algorithms (2006)、Apostolos Doxiadisと共に劇画(graphic novel) Logicomix (2009)Logicomix などを著している。
受賞歴 2002年 - クヌース賞 2004年 - IEEE Computer Society Charles Babbage Award 2011年 - 国立アテネ工科大学より名誉博士号 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. マイクロソフトの創設者の一人ビル・ゲイツ との共著論文がある。Gates W.H.; Papadimitriou, C.H. Bounds for sorting by prefix reversal.
私生活 2006年にカリフォルニア大学バークレー校で 教授と大学院生によるバンドLady X and The Positive Eigenvalues(レディXと正の固有値達)に参加している。
参考文献
外部リンク Christos Papadimitriou | Columbia Engineering：本人のウェブサイト