Christos Papadimitriou
Research Areas
Biography
He received his B.S.in EE from Athens Polytechnic, 1972, a M.S. in EE and Ph.D. in EECS from Princeton, 1974 and 1976 respectively. He is the C. Lester Hogan Professor of EECS. Professor Papadimitriou taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD before joining EECS at UC Berkeley January, 1996.
He has authored "Elements of the Theory of Computation", (Prentice-Hall 1982, with Harry Lewis, second edition September 1997), "Combinatorial Optimization: Algorithms and Complexity", (Prentice-Hall 1982, with Ken Steiglitz; second edition by Dover, 1998), "The Theory of Database Concurrency Control", (CS Press 1988), "Computational Complexity", (Addison Wesley, 1994), and "The Undergraduate Textbook Algorithms", (McGraw-Hill 2006, with Sanjoy Dasgupta and Umesh Vazirani). He has also written a novel about computation titled "Turing", (MIT Press 2003).
Selected Publications
- J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, "A BGP-based mechanism for lowest-cost routing," Distributed Computing, vol. 18, no. 1, pp. 61-72, July 2005.
- C. Papadimitriou, "Mythematics: Storytelling in the teaching of computer science and mathematics (Keynote Address)," ACM SIGSCE Bulletin: Special Issue on the 8th Annual ITCSE Conf., vol. 35, no. 3, pp. 1-1, Sep. 2003.
- A. Rao, C. Papadimitriou, S. Shenker, and I. Stoica, "Geographic routing without location information," in Proc. 9th Annual Intl. Conf. on Mobile Computing and Networking (MOBICOM '03), New York, NY: The Association for Computing Machinery, Inc., 2003, pp. 96-108.
- J. Feigenbaum, C. Papadimitriou, and S. Shenker, "Sharing the cost of multicast transmissions," J. Computer and System Sciences: Special Issue on Internet Algorithms, vol. 63, no. 1, pp. 21-41, Aug. 2001.
- C. Papadimitriou, P. Raghavan, H. Tamaki, and S. Vempala, "Latent semantic indexing: A probabilistic analysis," J. Computer and System Sciences, vol. 61, no. 2, pp. 217-235, Oct. 2000.
- E. Koutsoupias and C. Papadimitriou, "Worst-case equilibria," in Theoretical Aspects of Computer Science: Proc. 16th Annual Symp. on Theoretical Aspects of Computer Science (STACS '99), G. Meinel and S. Tison, Eds., Lecture Notes in Computer Science, Vol. 1563, Berlin, Germany: Springer-Verlag, 1999, pp. 404-413.
- C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, reprint ed., Mineola, NY: Dover Publications, 1998.
- H. R. Lewis and C. Papadimitriou, Elements of the Theory of Computation, 2nd ed., Upper Saddle River, NJ: Prentice-Hall, 1997.
- C. Papadimitriou and M. Yannakakis, "Towards an architecture-independent analysis of parallel algorithms," in Proc. 20th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 1988, pp. 510-513.
- C. Papadimitriou and M. Yannakakis, "Optimization, approximation, and complexity classes," in Proc. 20th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 1988, pp. 229-234.
- C. Papadimitriou, "The serializability of concurrent database updates," J. ACM, vol. 26, no. 4, pp. 631-653, Oct. 1979.
Awards, Memberships and Fellowships
- IEEE CS Women of ENIAC Computer Pioneer Award, 2022
- IEEE John von Neumann Medal, 2016
- Gold-Platinum ETH Medal for CS and CS Education, 2016
- EATCS Award, 2015
- Gödel Prize, 2012
- Diane S. McEntyre Award for Excellence in Teaching Computer Science, 2009
- National Academy of Sciences (NAS) Member, 2009
- Katayanagi Prize for Research Excellence, 2008
- Kalai Prize in Game Theory and Computer Science, 2008
- CS Charles Babbage Award, 2004
- ACM SIGACT Knuth Prize, 2002
- National Academy of Engineering (NAE) Member, 2002
- Association for Computing Machinery (ACM) Fellow, 2001
- ACM SIGMOD Best Paper Award, 2000
- ACM SIGMOD Best Paper Award, 1997
- American Academy of Arts and Sciences Member, 1990
