Christos Papadimitriou
DONOVAN FAMILY PROFESSOR OF COMPUTER SCIENCE; PROVOST'S SENIOR FACULTY TEACHING SCHOLAR
456 Computer Science Building
Mail Code 4721
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.
Research Interests
Theory of algorithms and complexity, and its applications to the study of databases, optimization, AI, the Internet, game theory, evolution, and the brainResearch Areas
AlgorithmsArtificial IntelligenceComputing SystemsData ScienceNeuroscience & NeuroengineeringRoboticsSustainable Humanity: WaterHealthy HumanityConnected HumanityCreative HumanityLinks
CVHe authored the widely used textbook Computational Complexity, as well as four others, and has written three novels, including the best-selling Logicomix and his latest, Independence. He considers himself fundamentally a teacher, having taught at UC Berkeley for the past 20 years, and before that at Harvard, MIT, the National Technical University of Athens, Stanford, and UC San Diego.
Papadimitriou has been awarded the Knuth Prize, IEEE’s John von Neumann Medal, the EATCS Award, the IEEE Computer Society Charles Babbage Award, and the Gödel Prize. He is a fellow of the Association for Computer Machinery and the National Academy of Engineering, and a member of the National Academy of Sciences.
He received his BS in Electrical Engineering from Athens Polytechnic in 1972. He has a MS in Electrical Engineering and a PhD in Electrical Engineering/Computer Science from Princeton, received in 1974 and 1976, respectively.
Professional Experience
- 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
Professional Affiliations
- Fellow, National Academy of Engineering (2002)
- Fellow, Association for Computer Machinery (2001)
- Elected to American Academy of Arts and Sciences (2001)
Honors & Awards
- 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
Selected Publications
- 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