Christos Papadimitriou

from Wikipedia, the free encyclopedia

Christos Charilaos Papadimitriou ( Greek Χρήστος Χαρίλαος Παπαδημητρίου ) (* 1949 in Athens ) is a Greek computer scientist .

Papadimitriou 2009

Career and research

Papadimitriou made 1972 his degree in Electrical Engineering at the National Technical University in Athens and then studied at the Princeton University , where he earned his master's degree in 1974 and 1976 doctorate was. He then taught at Harvard University , the Technical University of Athens, the Massachusetts Institute of Technology (MIT), Stanford University and the University of California, San Diego (UCSD). From 1996 he was a professor at the University of California, Berkeley , where he was a Miller Fellow in 1978 .

Papadimitriou deals with complexity theory , algorithm theory , databases , artificial intelligence , optimization , game theory , network theory and evolution theory from the point of view of information theory. With Mihalis Yannakakis , he introduced new complexity classes in 1988 ( Max-NP and its sub-class Max-SNP ), which also include known problems such as the traveling salesman problem and 3-SAT .

In 2001 he became a Fellow of the Association for Computing Machinery (ACM) and the American Academy of Arts and Sciences . He is a Fellow of the National Academy of Engineering and the National Academy of Sciences (2009) and an external member of the Academia Europaea (2006).

Papadimitriou has received several awards for his work. In 2002 he was awarded the Knuth Prize , 2008, together with Paul W. Goldberg and Constantinos Daskalakis the Kalai price of the Game Theory Society . In 2012 he received the Gödel Prize with his doctoral student Elias Koutsoupias for work on algorithmic game theory, especially the Price of Anarchy concept in their article Worst-Case Equilibria . In 2015 he was awarded the EATCS Award . For 2016 he was awarded the IEEE John von Neumann Medal and for 2018 the Harvey Prize .

With his PhD student Constantinos Daskalakis (2018 winner of the Nevanlinna Prize ), he applied complexity theory to calculating the Nash equilibrium in game theory (and economics).

In 1979 he published a paper with Bill Gates on the pancake sorting problem . He plays keyboard and sings in a campus rock band in Berkeley ( Lady X and the Positive Eigenvalues ), wrote a novel and comic (with Apostolos Doxiadis ) and published a collection of his articles in the Greek daily To Vima .

Fonts

  • with Harry R. Lewis: Elements of the theory of computation , Prentice-Hall 1982, 2nd edition 1997
  • with Kenneth Steiglitz: Combinatorial Optimization , Prentice Hall 1982, Dover 1998
  • Computational Complexity , Addison-Wesley 1994
  • with 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
  • with Apostolos Doxiadis , Alecos Papadatos , Annie di Donna: Logicomix: an epic search for truth . From the English by Ebi Naumann. Zurich: Atrium-Verlag, 2012
  • with Elias Koutsoupias: Worst-case equilibria, Computer Science Review, Volume 3, 2009, pp. 65-69
  • with Koutsoupias: Worst-case equilibria, Proceedings of the 16th annual conference on Theoretical aspects of computer science, 1999, 404-413
  • with Koutsoupias: On the k-server conjecture, Journal of the ACM, Volume 43, 1995, pp. 971-983
  • with Koutsoupias: Beyond competitive analysis, SIAM Journal on Computing Volume 30, 2000, pp. 300-317

Web links

Commons : Christos Papadimitriou  - collection of images, videos and audio files

Individual evidence

  1. ↑ Papadimitriou, Yannakakis: Optimization, approximation, and complexity classes , Proceedings of the 20th annual ACM symposium on Theory of computing, May 1988, pp. 229-234
  2. ^ Book of Members. Retrieved July 27, 2016 .
  3. ↑ Harvey Prize 2018
  4. ↑ Bounds for sorting by prefix reversal , Discrete Mathematics, Volume 27, 1979, pp. 47-57.
  5. ↑ A lifetime for hackers? , Kastaniotis Verlag 2004 (Greek)
personal data
SURNAME Papadimitriou, Christos
ALTERNATIVE NAMES Papadimitriou, Christos Charilaos (full name); Παπαδημητρίου, Χρήστος Χαρίλαος (Greek)
BRIEF DESCRIPTION Greek computer scientist
DATE OF BIRTH 1949
PLACE OF BIRTH Athens