Christos Papadimitriou

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

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

Papadimitriou deals with complexity theory, algorithms, theory, databases, artificial intelligence, optimization, game theory, network theory and evolutionary theory under the information-theoretical aspects.

With Mihalis Yannakakis he led 1988 new complexity classes (Max- NP and its subclass Max SNP), which include well-known problems such as the traveling salesman problem ends and 3-SAT.

In 2002 he received the Knuth Prize. He was a Fellow of the Association for Computing Machinery (ACM ) 2001. He is a Fellow of the National Academy of Engineering and the National Academy of Sciences ( 2009).

In 1979 he published a paper with Bill Gates about the pancake sorting problem.

In 2012 he was awarded the Gödel Prize with his doctoral Elias Koutsoupias for work on Algorithmic game theory, especially the Price of Anarchy concept in her essay Worst - Case Equilibria.

He plays keyboards and sings in a rock band campus in Berkeley (Lady X and the Positive Eigenvalues ​​), wrote a novel and a comic book ( with Apostolos Doxiadis ) and published a collection of his articles in the Greek daily To Vima.

Writings

  • 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
  • Sanjoy Dasgupta with, Umesh Vazirani: Algorithms, McGraw Hill 2006
  • The theory of database concurrency control, Computer Science Press 1986
  • Turing a novel about computation, MIT Press
  • Apostolos Doxiadis with: Logicomix: an epic search for truth, Bloomsbury Publishing, 2009 (a mixture of comic and novel)
  • 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 competive analysis, SIAM Journal on Computing Volume 30, 2000, pp. 300-317
Greece Boolean satisfiability problem#3-satisfiability Integrated Authority File
188165
de