Christos Papadimitriou

From Wikipedia, the free encyclopedia
  (Redirected from Christos H. Papadimitriou)
Jump to navigation Jump to search
Christos Papadimitriou
Christos Papadimitriou mg 7721-b.cr2.jpg
  • Christos Harilaos Papadimitriou
  • Greek: Χρήστος Χαρίλαος Παπαδημητρίου

(1949-08-16) August 16, 1949 (age 69)
Alma mater
Scientific career
ThesisThe Complexity of Combinatorial Optimization Problems (1972)
Doctoral advisorKenneth Steiglitz[3]
Doctoral students

Christos Harilaos Papadimitriou (Greek: Χρήστος Χαρίλαος Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist, and professor of Computer Science at Columbia University.[1][4][5][6][7]


Papadimitriou studied at the National Technical University of Athens, where in 1972 he received his Bachelor of Arts degree in Electrical Engineering. He continued to study at Princeton University, where he received his MS in Electrical Engineering in 1974 and his PhD in Electrical Engineering and Computer Science in 1976.


Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, UCSD, University of California, Berkeley and is currently the Donovan Family Professor of Computer Science at Columbia University.

Papadimitriou co-authored a paper on pancake sorting with Bill Gates, then a Harvard undergraduate. Papadimitriou recalled "Two years later, I called to tell him our paper had been accepted to a fine math journal. He sounded eminently disinterested. He had moved to Albuquerque, New Mexico to run a small company writing code for microprocessors, of all things. I remember thinking: 'Such a brilliant kid. What a waste.'"[8]

In 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize. He became fellow of the U.S. National Academy of Engineering for contributions to complexity theory, database theory, and combinatorial optimization.[9] In 2009 he was elected to the US National Academy of Sciences. During the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), there was a special event honoring Papadimitriou's contributions to computer science.[10] In 2012, he, along with Elias Koutsoupias, was awarded the Gödel Prize for their joint work on the concept of the price of anarchy.[11]

Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of computational complexity theory. He has also co-authored the textbook Algorithms (2006) with Sanjoy Dasgupta and Umesh Vazirani, and the graphic novel Logicomix (2009)[12] with Apostolos Doxiadis.

His name was listed in the 19th position on the CiteSeer search engine academic database and digital library[citation needed].

Honors and awards[edit]

In 1997, Papadimitriou received a doctorate honoris causa from the ETH Zurich.[13]

In 2011, Papadimitriou received a doctorate honoris causa from the National Technical University of Athens.[14]

In 2013, Papadimitriou received a doctorate honoris causa from the École polytechnique fédérale de Lausanne (EPFL).

Papadimitriou was awarded the IEEE John von Neumann Medal in 2016, the EATCS Award in 2015, the Gödel Prize in 2012, the IEEE Computer Society Charles Babbage Award in 2004, and the Knuth Prize in 2002.


Personal life[edit]

At UC Berkeley, in 2006, he joined a professor-and-graduate-student band called Lady X and The Positive Eigenvalues.[16]


  1. ^ a b Christos Papadimitriou publications indexed by Google Scholar
  2. ^ "Columbia Faculty". Retrieved 2017-08-05.
  3. ^ Christos Papadimitriou at the Mathematics Genealogy Project
  4. ^ Christos Papadimitriou author profile page at the ACM Digital Library
  5. ^ Ahmed, F (2014). "Profile of Christos Papadimitriou". Proceedings of the National Academy of Sciences. 111 (45): 15858–60. Bibcode:2014PNAS..11115858A. doi:10.1073/pnas.1405579111. PMC 4234580. PMID 25349396.
  6. ^ Christos H. Papadimitriou at DBLP Bibliography Server Edit this at Wikidata
  7. ^ Christos Papadimitriou's publications indexed by the Scopus bibliographic database. (subscription required)
  8. ^ "Professor who knew Bill Gates as a student at Harvard: He was the smartest person I've ever met". Business Insider. Retrieved 2018-05-06.
  9. ^ "Member Directory at NAE Website". Retrieved 2017-07-22.
  10. ^ "Special Events: Honoring Christos Papadimitriou Scientific Contribution to Computer Science". ICALP 2009 – 36th International Colloquium on Automata, Languages and Programming. Archived from the original on March 6, 2012.
  11. ^ "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 16 May 2012. Archived from the original on 18 July 2013. Retrieved 16 May 2012.
  12. ^ Logicomix
  13. ^ "Honorary Doctorates, Department of Computer Science". Retrieved 2017-07-22.
  14. ^ "Live feed from the Award Ceremony of an honorary doctorate from the NTUA to the UC Berkeley Professor Chr. Papadimitriou". Archived from the original on 2016-03-03. Retrieved 2014-06-17.
  15. ^ Gates, William H.; Papadimitriou, Christos H. (1979). "Bounds for sorting by prefix reversal". Discrete Mathematics. 27: 47–57. doi:10.1016/0012-365X(79)90068-2.
  16. ^ "Engineers rock — Out of the EECS department comes a hot new band". Archived from the original on May 31, 2013. Retrieved 2013-12-29.