Christos Papadimitriou


456 Computer Science Building
Mail Code 4721

Tel(212) 853-8429

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 brain

Papadimitriou 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

Honors & Awards