World Library  
Flag as Inappropriate
Email this Article

Christos Papadimitriou

Article Id: WHEBN0003509428
Reproduction Date:

Title: Christos Papadimitriou  
Author: World Heritage Encyclopedia
Language: English
Subject: Joseph S. B. Mitchell, Logicomix, Pancake sorting, Witsenhausen's counterexample, Mihalis Yannakakis
Collection: 1949 Births, American Technology Writers, American Writers of Greek Descent, Fellows of the Association for Computing MacHinery, Gödel Prize Laureates, Greek Computer Scientists, Greek Emigrants to the United States, Harvard University Faculty, Knuth Prize Laureates, Living People, Massachusetts Institute of Technology Faculty, Members of the United States National Academy of Engineering, Members of the United States National Academy of Sciences, National Technical University of Athens Alumni, Princeton University Alumni, Stanford University School of Engineering Faculty, Theoretical Computer Scientists, University of California, Berkeley College of Engineering Faculty, University of California, Berkeley Faculty, University of California, San Diego Faculty
Publisher: World Heritage Encyclopedia

Christos Papadimitriou

Christos Papadimitriou
  • Christos Harilaos Papadimitriou
  • Greek: Χρήστος Χαρίλαος Παπαδημητρίου

(1949-08-16) August 16, 1949
Alma mater
Thesis The Complexity of Combinatorial Optimization Problems (1972)
Doctoral advisor Kenneth Steiglitz[2]
Doctoral students
Notable awards

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


  • Education 1
  • Career 2
  • Honors and awards 3
  • Publications 4
  • Personal life 5
  • References 6


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, and UCSD, and is currently C. Lester Hogan Professor of Electrical Engineering and Computer Science at U.C. Berkeley.

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 US National Academy of Engineering for contributions to complexity theory, database theory, and combinatorial optimization.[7] 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.[8] 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.[9]

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)[10] with Apostolos Doxiadis.

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

Honors and awards

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

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

Papadimitriou was also awarded the EATCS Award in 2015, the Gödel Prize in 2012 and the Knuth Prize in 2002.


  • Elements of the Theory of Computation (with Harry R. Lewis). Prentice-Hall, 1982; second edition September 1997. greek edition
  • Combinatorial Optimization: Algorithms and Complexity (with Kenneth Steiglitz). Prentice-Hall, 1982; second edition, Dover, 1998.
  • The Theory of Database Concurrency Control. CS Press, 1986.
  • Computational Complexity. Addison Wesley, 1994.
  • Turing (a Novel about Computation). MIT Press, November 2003.
  • Life Sentence to Hackers? (in Greek). Kastaniotis Editions, 2004. A compilation of articles written for the Greek newspaper To Vima.
  • Algorithms (coauthored with Sanjoy Dasgupta and Umesh Vazirani). McGraw-Hill, September 2006
  • Logicomix, An Epic Search for Truth (coauthored with Apostolos Doxiadis, with artwork by Alecos Papadatos and Annie di Donna). Bloomsbury Publishing and Bloomsbury USA, September 2009.
  • He co-authored a paper with Bill Gates, co-founder of Microsoft.[12]

Personal life

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


  1. ^ a b Christos Papadimitriou's publications indexed by Google Scholar, a service provided by Google
  2. ^ a b Christos Papadimitriou at the Mathematics Genealogy Project
  3. ^ Christos Papadimitriou from the Association for Computing Machinery (ACM) Digital Library
  4. ^ Ahmed, F (2014). "Profile of Christos Papadimitriou". Proceedings of the National Academy of Sciences 111: 15858–60.  
  5. ^ Christos Papadimitriou's publications indexed by the DBLP Bibliography Server at the University of Trier
  6. ^ Christos Papadimitriou's publications indexed by the Scopus bibliographic database, a service provided by Elsevier.
  7. ^ National Academy of Engineering, Members by Last Name: P
  8. ^ "Special Events: Honoring Christos Papadimitriou Scientific Contribution to Computer Science". ICALP 2009 – 36th International Colloquium on Automata, Languages and Programming. 
  9. ^ "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 16 May 2012. Retrieved 16 May 2012. 
  10. ^ Logicomix
  11. ^ "Live feed from the Award Ceremony of an honorary doctorate from the NTUA to the UC Berkeley Professor Chr. Papadimitriou". 
  12. ^ Gates W.H.; Papadimitriou, C.H. Bounds for sorting by prefix reversal. Discrete Math. 27 (1979), 47–57.
  13. ^ "Engineers rock — Out of the EECS department comes a hot new band". Retrieved 2013-12-29. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.