Christos Papadimitriou

Professor

Research Areas

• Biosystems & Computational Biology (BIO)
• Database Management Systems (DBMS)
• Theory (THY)

Research Centers

• Berkeley Center for New Media (BCNM)

Teaching Schedule (Spring 2008)

• CS 298-2. Theory Seminar, M 4:00-5:30P, 438 Soda

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," ACM SIGSCE Bulletin, 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, New York, NY: ACM Press, 2003, pp. 96-108.
• J. Feigenbaum, C. Papadimitriou, and S. Shenker, "Sharing the cost of multicast transmissions," J. Computer and System Sciences, 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 Lecture Notes in Computer Science: Theoretical Aspects of Computer Science, G. Meinel and S. Tison, Eds., Vol. 1563, Berlin, Germany: Springer-Verlag, 1999, pp. 387-396.
• 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.