Christos Papadimitriou

Christos Charilaos Papadimitriou (griechisch Χρήστος Χαρίλαος Παπαδημητρίου) (* 1949 in Athen) ist ein griechischer Informatiker.

Papadimitriou 2009

Werdegang und Forschung

Papadimitriou machte 1972 sein Diplom in Elektrotechnik an der Nationalen Technischen Universität in Athen und studierte dann an der Princeton University, wo er 1974 seinen Master-Abschluss machte und 1976 promoviert wurde. Danach lehrte er an der Harvard University, der TU Athen, am Massachusetts Institute of Technology (MIT), der Stanford University sowie der University of California, San Diego (UCSD). Ab 1996 war er Professor an der University of California, Berkeley, wo er schon 1978 als Miller Fellow war.

Papadimitriou befasst sich mit Komplexitätstheorie, Algorithmentheorie, Datenbanken, Künstlicher Intelligenz, Optimierung, Spieltheorie, Netzwerktheorie sowie Evolutionstheorie unter informationstheoretischen Aspekten. Mit Mihalis Yannakakis führte er 1988 neue Komplexitätsklassen ein (Max-NP und dessen Unterklasse Max-SNP), zu denen auch bekannte Probleme wie das Problem des Handlungsreisenden und 3-SAT gehören.

2001 wurde er Fellow der Association for Computing Machinery (ACM) sowie der American Academy of Arts and Sciences. Er ist Fellow der National Academy of Engineering und der National Academy of Sciences (2009) sowie auswärtiges Mitglied der Academia Europaea (2006).

Für seine Arbeiten wurde Papadimitriou mehrfach ausgezeichnet. 2002 erhielt er den Knuth-Preis, 2008 zusammen mit Paul W. Goldberg und Constantinos Daskalakis den Kalai-Preis der Game Theory Society. 2012 erhielt er den Gödel-Preis mit seinem Doktoranden Elias Koutsoupias für Arbeiten zur Algorithmischen Spieltheorie, speziell des Price of Anarchy Konzepts in ihrem Aufsatz Worst-Case Equilibria. 2015 wurde er mit dem EATCS-Award ausgezeichnet. Für 2016 wurde ihm die IEEE John von Neumann Medal zugesprochen und für 2018 der Harvey-Preis, für 2022 der Computer Pioneer Award.

Mit seinem Doktoranden Constantinos Daskalakis (2018 Gewinner des Nevanlinna-Preises) wandte er Komplexitätstheorie auf die Berechnung des Nash-Gleichgewichts in der Spieltheorie (und den Wirtschaftswissenschaften) an.

1979 veröffentlichte er eine Arbeit zusammen mit Bill Gates über das Pfannkuchen-Sortierproblem. Er spielt Keyboard und singt in einer Campus-Rockband in Berkeley (Lady X and the Positive Eigenvalues), schrieb einen Roman und einen Comic (mit Apostolos Doxiadis) und veröffentlichte eine Sammlung seiner Artikel in der griechischen Tageszeitung To Vima.

Schriften

• mit Harry R. Lewis: Elements of the theory of computation, Prentice-Hall 1982, 2. Auflage 1997
• mit Kenneth Steiglitz: Combinatorial Optimization, Prentice Hall 1982, Dover 1998
• Computational Complexity, Addison-Wesley 1994
• mit Sanjoy Dasgupta, Umesh Vazirani: Algorithms, McGraw Hill 2006
• The theory of database concurrency control, Computer Science Press 1986
• Turing—a novel about computation, MIT Press
• mit Apostolos Doxiadis, Alecos Papadatos, Annie di Donna: Logicomix : eine epische Suche nach Wahrheit. Aus dem Engl. von Ebi Naumann. Zürich : Atrium-Verlag, 2012
• mit Elias Koutsoupias: Worst-case equilibria, Computer Science Review, Band 3, 2009, S. 65–69
• mit Koutsoupias: Worst-case equilibria, Proceedings of the 16th annual conference on Theoretical aspects of computer science, 1999, 404–413
• mit Koutsoupias: On the k-server conjecture, Journal of the ACM, Band 43, 1995, S. 971–983
• mit Koutsoupias: Beyond competitive analysis, SIAM Journal on Computing Band 30, 2000, S. 300–317

Weblinks

Commons

Commons: Christos Papadimitriou – Sammlung von Bildern, Videos und Audiodateien

• Literatur von und über Christos Papadimitriou im Katalog der Deutschen Nationalbibliothek
• Homepage