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). Er ist Fellow der National Academy of Engineering und der National Academy of Sciences (2009).

1979 veröffentlichte er eine Arbeit zusammen mit Bill Gates.^[2]

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.^[3]

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: Logicomix: an epic search for truth, Bloomsbury Publishing, 2009 (eine Mischung aus Comic und Roman)

Weblinks

• Homepage

Einzelnachweise

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

Normdaten: PND: 135731909 (PICA) | LCCN: n80102786 | VIAF: 37007186 | WorldCat | WP-Personeninfo