Christos Papadimitriou

Education

Papadimitriou studied at the National Technical University of Athens, where in 1972 he received his Bachelor of Arts degree in electrical engineering. He then pursued graduate studies at Princeton University, where he received his Ph.D. in electrical engineering and computer science in 1976 after completing a doctoral dissertation titled "The complexity of combinatorial optimization problems."

Career

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.'" The company was Microsoft.

Papadimitriou co-authored "The Complexity of Computing a Nash Equilibrium" with his students Constantinos Daskalakis and Paul W. Goldberg, for which they received the 2008 Kalai Game Theory and Computer Science Prize from the Game Theory Society for "the best paper at the interface of game theory and computer science", in particular "for its key conceptual and technical contributions"; and the Outstanding Paper Prize from the Society for Industrial and Applied Mathematics.

In 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize. Also in 2002, he became a member of the U.S. National Academy of Engineering for contributions to complexity theory, database theory, and combinatorial optimization.{{cite web | access-date=2017-07-22}} 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.{{cite web | url-status=dead | archive-url=https://web.archive.org/web/20120306104025/http://icalp09.cti.gr/index.php/Main/SpecialEvents | archive-date=March 6, 2012

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) 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 1997, Papadimitriou received a doctorate honoris causa from the ETH Zurich.

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

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. In 2019 he received the Harvey Prize of the Technion/Israel for the year 2018.

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 2008
• 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, on pancake sorting.

Personal life

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

References

References

1. {{MathGenealogy
2. (24 May 2018). "Christos Papadimitriou".
3. {{GoogleScholar. ZDvxbWYAAAAJ
4. {{ACMPortal
5. {{DBLP
6. {{Scopus
7. (1976). "The complexity of combinatorial optimization problems".
8. "People of ACM — Christos Papadimitriou". People of ACM.
9. "Game Theory Society: Named Lectures and Prizes".
10. "Prize in Game Theory and Computer Science of the Game Theory Society (2008)".
11. (16 May 2012). "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory".
12. [http://www.logicomix.com/en Logicomix]
13. "Honorary Doctorates, Department of Computer Science".
14. "Live feed from the Award Ceremony of an honorary doctorate from the NTUA to the UC Berkeley Professor Chr. Papadimitriou".
15. [https://www.technion.ac.il/en/2019/10/technion-to-award-harvey-prize/ Harvey Prize 2018]
16. (1979). "Bounds for sorting by prefix reversal". Discrete Mathematics.
17. "Engineers rock — Out of the EECS department comes a hot new band".