Christos Papadimitriou

Computer Science

One of world’s leading computer science theorists, Christos Papadimitriou is best known for his work in computational complexity, helping to expand its methodology and reach. He has also explored other fields through what he calls the algorithmic lens, having contributed to biology and the theory of evolution, economics, and game theory (where he helped found the field of algorithmic game theory), artificial intelligence, robotics, networks and the Internet, and more recently the study of the brain. 

  • The Donovan Family Professor of Computer Science, 2017 –
  • UC Berkeley,  1996-2017, where he was the C. Lester Hogan Professor of Electrical Engineering and Computer Science
  • Professor, National Technical University of Athens, 1981-1988
  • Papadimitriou has also taught at Harvard, MIT, Athens Polytechnic, Stanford, and UC, San Diego
  • Fellow, National Academy of Engineering (2002)
  • Fellow, Association for Computer Machinery (2001)
  • Elected to American Academy of Arts and Sciences (2001)
  • IEEE John von Neumann Medal, 2016
  • EATCS Award, 2015
  • Gödel Prize, 2012, along with Elias Koutsoupias
  • Elected to US National Academy of Sciences, 2009
  • IEEE Computer Society Charles Babbage Award, 2004
  • Knuth Prize, 2002
  • Elements of the Theory of Computation (with Harry R. Lewis), 1982 and 1997
  • Combinatorial Optimization: Algorithms and Complexity (with Kenneth Steiglitz), 1998
  • The Theory of Database Concurrency Control, 1986
  • Computational Complexity, 1994
  • Turing (a Novel about Computation), 2003
  • Algorithms (coauthored with Sanjoy Dasgupta and Umesh Vazirani), 2006
  • Logicomix, An Epic Search for Truth (coauthored with Apostolos Doxiadis, with artwork by Alecos Papadatos and Annie di Donna), 2009