Christos Papadimitriou

Christos Papadimitriou
Born	Christos Harilaos Papadimitriou Greek: Χρήστος Χαρίλαος Παπαδημητρίου (1949-08-16) August 16, 1949 Athens
Fields	Algorithms Complexity Game theory Evolution[1]
Institutions	University of California, Berkeley Harvard University MIT Athens Polytechnic Stanford University UCSD
Alma mater	Athens Polytechnic (BS) Princeton University (PhD)
Thesis	The Complexity of Combinatorial Optimization Problems (1972)
Doctoral advisor	Kenneth Steiglitz[2]
Doctoral students	Esther Arkin Ziv Bar-Yossef Kamalika Chaudhuri Constantinos Daskalakis Xiaotie Deng Alex Fabrikant Deborah Goldman Paris Kanellakis Elias Koutsoupias Joseph Mitchell Alan Murray Edouard Servan-Schreiber Kunal Talwar Christopher Umans Stephen Vavasis[2]
Notable awards	Von Neumann Medal (2016) EATCS Award (2015) Gödel Prize (2012) Knuth Prize (2002)
Website www.cs.berkeley.edu/~christos

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

Education

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.

Career

Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, and UCSD, and is currently the 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 U.S. 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 awarded the IEEE John von Neumann Medal in 2016, the EATCS Award in 2015, the Gödel Prize in 2012 and the Knuth Prize in 2002.

Publications

• 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]

References

Wikimedia Commons has media related to Christos Papadimitriou.