Christos Papadimitriou

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

Papadimitriou 2009

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.[1]

2002 erhielt er den Knuth-Preis. 2001 wurde er Fellow der Association for Computing Machinery (ACM) sowie der American Academy of Arts and Sciences.[2] Er ist Fellow der National Academy of Engineering und der National Academy of Sciences (2009) sowie auswärtiges Mitglied der Academia Europaea (2006).

1979 veröffentlichte er eine Arbeit zusammen mit Bill Gates über das Pfannkuchen-Sortierproblem.[3]

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.

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.

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.[4]

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 competive analysis, SIAM Journal on Computing Band 30, 2000, S. 300–317

Weblinks

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

Homepage

Einzelnachweise
Papadimitriou, Yannakakis: Optimization, approximation, and complexity classes, Proceedings of the 20th annual ACM symposium on Theory of computing, Mai 1988, S. 229–234
Book of Members. Abgerufen am 27. Juli 2016 (englisch).
Bounds for sorting by prefix reversal, Discrete Mathematics, Band 27, 1979, S. 47–57.
Lebenslang für Hacker?, Kastaniotis Verlag 2004 (griechisch)