クリストス・ハリラオス・パパディミトリウ（ギリシャ語: Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου、1949年8月16日生まれ）は、ギリシャ系アメリカ人の理論計算機科学者であり、コロンビア大学のドノバン・ファミリー計算機科学教授である。彼の研究は、計算複雑性理論、アルゴリズム、データベース理論、およびアルゴリズム的ゲーム理論に及び、その貢献は計算における理論的基盤と実用的応用の両方を形成してきた。彼は、無秩序の代償、ナッシュ均衡の複雑性に関する研究、そして論理の歴史に関する影響力のある教科書やグラフィックノベルの執筆で広く知られている。
パパディミトリウの経歴は、計算機科学と経済学、数学、さらには神経科学を結びつける学際的な洞察によって特徴づけられる。エリアス・クツピアスと共同で開発した無秩序の代償に関する研究は、分散型意思決定の非効率性を定量化する枠組みを確立し、この概念は現在アルゴリズム的ゲーム理論の中心となっている。複雑性理論への貢献は、コンピュータが効率的に計算できる限界を明確にし、最適化、データベースシステム、人工知能に影響を与えている。
教育
パパディミトリウはアテネ国立工科大学で学び、1972年に統合修士課程を通じて電気工学の学位を取得した。その後、プリンストン大学で大学院研究を続け、1976年に電気工学および計算機科学の博士号を取得した。博士論文は「組合せ最適化問題の複雑性」と題され、後の最適化タスクの計算困難性に関する研究の基礎を築いた。
学術経歴
パパディミトリウは、ハーバード大学、マサチューセッツ工科大学（MIT）、アテネ国立工科大学、スタンフォード大学、カリフォルニア大学サンディエゴ校、カリフォルニア大学バークレー校など、複数の主要機関で教職を歴任してきた。2014年以降、彼はコロンビア大学のドノバン・ファミリー計算機科学教授を務め、理論計算機科学の研究を引き続き主導している。
彼の初期の経歴で最も注目すべき出来事の一つは、当時ハーバード大学の学部生だったビル・ゲイツとのパンケーキソーティングに関する論文の共同研究である。この問題は、パンケーキのスタックを接頭辞を反転させて再配置することを含む。この論文は数学ジャーナルに掲載され、パパディミトリウは後に、ゲイツに受理を伝えたとき、アルバカーキに移って小さなソフトウェア会社を経営していたゲイツは関心を示さなかったようだと回想している。その会社がマイクロソフトだった。
複雑性理論への貢献
パパディミトリウの計算複雑性の研究は基礎的である。彼の教科書『計算複雑性』（1994年）は、この分野で最も広く使用されている参考書の一つであり、基本的な複雑性クラスから確率的および対話型証明システムの高度な結果までを扱っている。彼はまた、データベースの並行性制御理論、組合せ最適化、および推論や計画を含む人工知能の問題の複雑性にも貢献してきた。
彼の学生であるコンスタンティノス・ダスカラキスおよびポール・W・ゴールドバーグと共同執筆したナッシュ均衡の計算複雑性に関する研究は、特定のゲームにおけるナッシュ均衡を見つけることが計算的に困難であることを示し、この結果はアルゴリズム的ゲーム理論と経済学に深い影響を与えている。この研究により、彼らは2008年にゲーム理論学会からカライ・ゲーム理論および計算機科学賞を、産業応用数学学会から優秀論文賞を受賞した。
アルゴリズム的ゲーム理論と無秩序の代償
パパディミトリウとエリアス・クツピアスとの無秩序の代償に関する共同研究は、エージェントの自己利益行動によってシステムの性能がどの程度低下するかを測定する指標を導入した。この概念は、ネットワークルーティング、資源配分、市場設計に応用され、分散型システムにおける非効率性を理解するための理論的基盤を提供している。この研究により、彼らは理論計算機科学における最高の栄誉の一つである2012年のゲーデル賞を受賞した。
彼のアルゴリズム的ゲーム理論への貢献は、メカニズムデザインや大規模システムにおける均衡の研究にまで及び、これらの分野はオンラインプラットフォームやマルチエージェント人工知能システムの台頭とともにますます重要になっている。
栄誉と賞
パパディミトリウは、その経歴を通じて数多くの栄誉を受けてきた。1997年にはチューリッヒ工科大学から名誉博士号を授与された。2001年には計算機協会のフェローに選出され、2002年にはクヌース賞を受賞し、米国工学アカデミーに選出された。2009年には米国科学アカデミーに選出された。2004年にはIEEEコンピュータソサエティのチャールズ・バベッジ賞、2015年にはEATCS賞、2016年にはIEEEジョン・フォン・ノイマンメダルを受賞した。2019年には、2018年分のテクニオン/イスラエルのハーベイ賞を受賞した。また、2011年にアテネ国立工科大学から、2013年にスイス連邦工科大学ローザンヌ校（EPFL）から名誉博士号を授与された。
出版物とアウトリーチ
パパディミトリウは、いくつかの影響力のある書籍の著者または共著者である。『計算理論の要素』（ハリー・R・ルイスと共著、1982年）は、オートマトン理論と形式言語に関する古典的な教科書である。『組合せ最適化：アルゴリズムと複雑性』（ケネス・スタイグリッツと共著、1982年）は、最適化問題のためのアルゴリズムの設計と解析を扱っている。『データベース並行性制御の理論』（1986年）は、データベースシステムの問題に対処している。彼の『計算複雑性』（1994年）は、標準的な参考書として残っている。
彼はまた、より広い読者向けの著作も執筆している。『チューリング（計算に関する小説）』（2003年）は、アラン・チューリングの生涯と思想を探求する小説である。『ロジコミックス：真実の探求の叙事詩』（2009年、アポストロス・ドキアディスと共著、アレコス・パパダトスとアニー・ディ・ドンナがイラストを担当）は、バートランド・ラッセルからクルト・ゲーデルまでの数学と論理の基礎の物語を描いたグラフィックノベルである。彼はまた、サンジョイ・ダスグプタおよびウメシュ・ヴァジラニと共著の教科書『アルゴリズム』（2006年）も執筆しており、これは計算機科学教育で広く使用されている。
私生活
パパディミトリウは、学術界を超えた創造的な活動に従事していることで知られている。2006年にカリフォルニア大学バークレー校で、彼は教授と大学院生によるバンド「レディXと正の固有値」に参加し、音楽と協力への関心を反映していた。
遺産と影響
パパディミトリウの研究は、理論計算機科学とその応用に永続的な影響を与えてきた。無秩序の代償と均衡の複雑性に関する彼の研究は、ネットワーク工学、経済学、人工知能など多様な分野に影響を与えている。彼の教科書は何世代もの計算機科学者を教育し、小説やグラフィックノベルを通じて複雑なアイデアを伝える彼の能力は、計算の歴史をより広い一般市民に届けてきた。2020年代初頭の時点で、彼は引き続き活発な研究者であり、計算、進化、脳の間のつながりを探求しており、Artificial intelligenceおよびMachine learningへの影響を持つ。
計算理論への彼の貢献は、Neural networkアーキテクチャやLarge language modelを含む現代のAIシステムの開発にも情報を提供し、学習と推論の計算上の限界と可能性についてのより深い理解を提供している。組合せ最適化と複雑性に関する彼の研究は、Deep learningやGenerative AIなどの分野における効率的なアルゴリズムの設計に関連し続けている。
パパディミトリウの遺産は、彼の技術的業績だけでなく、抽象理論と実用的応用の間のギャップを埋めるコミュニケーターおよび教育者としての役割によって定義されており、計算およびその先における応用に及んでいる。