From Wikipedia, the free encyclopedia

Professor Christos Papadimitriou giving a talk at the EPFL on 30 June 2009

Christos Harilaos Papadimitriou (Greek: Χρίστος Χαριλάου Παπαδημητρίου) is a Professor in the Computer Science Division at the University of California, Berkeley, United States. He studied at the National Technical University of Athens (BS in Electrical Engineering, 1972) and at Princeton University (MS in Electrical Engineering, 1974 and PhD in Electrical Engineering and Computer Science, 1976). He has also taught at Harvard, MIT, the National Technical University of Athens, Stanford, and UCSD.

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 Algorithms with Sanjoy Dasgupta and Umesh Vazirani. The book was published in 2006.

He is featured among the top 100 computer science authors and his name was listed in the 19th position on the CiteSeer search engine academic database and digital library.

Awards and honors

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.^[1] 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.^[2]

Interesting facts

• He co-authored a paper with Bill Gates, co-founder of Microsoft, while Gates was studying at Harvard.^[3]
• At UC Berkeley, in 2006, he joined a professor-and-graduate-student band called Lady X and The Positive Eigenvalues.

Bibliography

• Elements of the Theory of Computation (with Harry R. Lewis). Prentice-Hall, 1982; second edition September 1997.
• 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.

Notes

External links

• Home page at Berkeley
• Logicomix