

Christos Papadimitriou
Professor
Research Areas
Research Centers
Teaching Schedule
(Spring 2015)
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", (PrenticeHall 1982, with Harry Lewis, second edition September 1997), "Combinatorial Optimization: Algorithms and Complexity", (PrenticeHall 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", (McGrawHill 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 BGPbased mechanism for lowestcost routing," Distributed Computing, vol. 18, no. 1, pp. 6172, 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. 11, 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. 96108.
 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. 2141, 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. 217235, Oct. 2000.
 E. Koutsoupias and C. Papadimitriou, "Worstcase 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: SpringerVerlag, 1999, pp. 404413.
 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: PrenticeHall, 1997.
 C. Papadimitriou and M. Yannakakis, "Towards an architectureindependent analysis of parallel algorithms," in Proc. 20th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 1988, pp. 510513.
 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. 229234.
 C. Papadimitriou, "The serializability of concurrent database updates," J. ACM, vol. 26, no. 4, pp. 631653, Oct. 1979.



