Christos Papadimitriou
DONOVAN FAMILY PROFESSOR OF COMPUTER SCIENCE; PROVOST'S SENIOR FACULTY TEACHING SCHOLAR
456 Computer Science Building
Mail Code 4721
Christos Papadimitriou works on the theory of algorithms and complexity, aiming to expand the field's methodology and reach. His research often explores areas beyond computer science through what he calls the algorithmic lens: biology and the theory of evolution, economics and game theory (where he helped found the field of algorithmic game theory), artificial intelligence and robotics, networks and the Internet and, since 2013, the study of the brain and language. In this endeavor, Papadimitriou and his co-authors strive to bridge the gap between neurons and cognition -- between the brain and the mind -- by articulating formal models of the neural brain in which emergent behaviors can be proved formally, as well as brain-like artifacts capable of emulating complex cognitive phenomena, most recently natural language acquisition.
Research Interests
Theory of algorithms and complexity, and its applications to the study of databases, optimization, AI, the Internet, game theory, evolution, and the brainLinks
CVPapadimitriou considers himself fundamentally a teacher, having taught at UC Berkeley for 22 years before coming to Columbia in 2017, and before that at Harvard, MIT, the National Technical University of Athens, Stanford, and UC San Diego. He authored the textbooks Computational Complexity, Combinatorial Optimization, Algorithms, and Elements of theTheory of Computation. He has also written novels, sometimes with an educational aspiration, including the NYT best-seller Logicomix and his latest, Independence.
Papadimitriou is a member of the National Academy of Sciences and the National Academy of Engineering, a fellow of the American Association of Arts and Sciences, and the recipient of the Knuth Prize, the Gödel prize, the EATCS award, IEEE’s John von Neumann Medal, the IEEE Computer Society Charles Babbage Award, Technion's 2019 Harvey Prize, ACM EC's inaugural career award, IEEE's Women of the Edvac Computer Pioneer Award, and ACM EC's inaugural career award. In 2015, the president of the Hellenic Republic named him a commander of the order of the phoenix.
He received his BS in Electrical Engineering from Athens Polytechnic in 1972, and his PhD from Princeton in 1976. He has also received nine honorary doctorates, including from ETH (Zurich), EPFL (Lausanne), and the Universities of Paris (Dauphine), Cyprus and Athens.
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