Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

Faculty Publications - Christos Papadimitriou

Books

  • S. Dasgupta, C. H. Papadimitriou, and U. Vazirani, Algorithms, Boston, MA: McGraw-Hill Higher Education, 2006. [abstract]
  • H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, 2nd ed., Upper Saddle River, NJ: Prentice-Hall, 1998. [abstract]
  • C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, reprint ed., Mineola, NY: Dover Publications, 1998. [abstract]
  • H. R. Lewis and C. Papadimitriou, Elements of the Theory of Computation, 2nd ed., Upper Saddle River, NJ: Prentice-Hall, 1997. [abstract]
  • C. H. Papadimitriou, Computational Complexity, Reading, MA: Addison-Wesley, 1994. [abstract]
  • C. H. Papadimitriou, The Theory of Database Concurrency Control, Principles of Computer Science Series, Rockville, MD: Computer Science Press, 1986. [abstract]
  • H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall Software Series, Englewood Cliffs, NJ: Prentice-Hall, 1981. [abstract]

Book chapters or sections

  • T. Ito, E. D. Demaine, N. J. A. Harvey, C. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno, "On the complexity of reconfiguration problems," in Algorithms and Computation: Proc. 19th Intl. Symp. (ISAAC 2008), S. H. Hong, H. Nagamochi, and T. Fukunaga, Eds., Lecture Notes in Computer Science, Vol. 5369, Berlin, Germany: Springer-Verlag, 2008, pp. 28-39.
  • A. Hall, E. Nikolova, and C. Papadimitriou, "Incentive-compatible interdomain routing with linear utilities," in Internet and Network Economics: Proc. 3rd Intl. Workshop (WINE 2007), X. Deng and F. Graham, Eds., Lecture Notes in Computer Science, Vol. 4858, Berlin, Germany: Springer-Verlag, 2008, pp. 232-234.
  • K. Daskalakis, A. Mehta, and C. Papadimitriou, "A note on approximate Nash equilibria," in Internet and Network Economics: Proc. 2nd Intl. Workshop (WINE 2006), P. G. Spirakis, M. Mavronicolas, and S. G. Kontogiannis, Eds., Lecture Notes in Computer Science, Vol. 4286, Berlin, Germany: Springer-Verlag, 2007, pp. 297-306.
  • K. Daskalakis, A. Fabrikant, and C. Papadimitriou, "The game world is flat: The complexity of Nash equilibria in succinct games," in Automata, Languages and Programming: Proc. 33rd Intl. Colloquium (ICALP 2006). Part I, M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, Eds., Lecture Notes in Computer Science, Vol. 4051, Berlin, Germany: Springer-Verlag, 2006, pp. 513-524.
  • P. Gopalan, P. G. Kolaitis, E. N. Maneva, and C. Papadimitriou, "The connectivity of Boolean satisfiability: Computational and structural dichotomies," in Automata, Languages and Programming: Proc. 33rd Intl. Colloquium (ICALP 2006). Part I, M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, Eds., Lecture Notes in Computer Science, Vol. 4051, Berlin, Germany: Springer-Verlag, 2006, pp. 346-357.
  • G. Kouroupas, E. Koutsoupias, C. Papadimitriou, and M. Sideri, "Experiments with an economic model of the World Wide Web," in Internet and Network Economics: Proc. 1st Intl. Workshop (WINE 2005), X. Deng and Y. Ye, Eds., Lecture Notes in Computer Science, Vol. 3828, Berlin, Germany: Springer-Verlag, 2006, pp. 46-54.
  • K. Daskalakis and C. Papadimitriou, "The complexity of games on highly regular graphs," in Algorithms: Proc. 13th Annual European Symp. (ESA 2005), G. S. Brodal and S. Leonardi, Eds., Lecture Notes in Computer Science, Vol. 3669, Berlin, Germany: Springer-Verlag, 2005, pp. 71-82.
  • A. Hall and C. Papadimitriou, "Approximating the distortion," in Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, C. Chekuri, K. Jansen, J. D. P. Rolim, and L. Trevisan, Eds., Lecture Notes in Computer Science, Vol. 3624, Berlin, Germany: Springer-Verlag, 2005, pp. 111-122.
  • V. Koltun and C. Papadimitriou, "Approximately dominating representatives," in Database Theory: Proc. 10th Intl. Conf. (ICDT 2005), T. Eiter and L. Libkin, Eds., Lecture Notes in Computer Science, Vol. 3363, Berlin, Germany: Springer-Verlag, 2005, pp. 204-214.
  • C. Papadimitriou and D. Ratajczak, "On a conjecture related to geometric routing," in Algorithmic Aspects of Wireless Sensor Networks: Proc. 1st Intl. Workshop (ALGOSENSORS 2004), S. Nikoletseas and J. D. P. Rolim, Eds., Lecture Notes in Computer Science, Vol. 3121, Berlin, Germany: Springer-Verlag, 2004, pp. 9-17.
  • J. Elson, R. M. Karp, C. Papadimitriou, and S. Shenker, "Global synchronization in sensornets," in LATIN 2004: Theoretical Informatics--Proc. 6th Latin American Symp., M. Farach-Colton, Ed., Lecture Notes in Computer Science, Vol. 2976, Berlin, Germany: Springer-Verlag, 2004, pp. 609-624.
  • M. Mihail and C. Papadimitriou, "On the eigenvalue power law," in Randomization and Approximation Techniques in Computer Science (RANDOM 2002), J. D. P. Rolim and S. Vadhan, Eds., Lecture Notes in Computer Science, Vol. 2483, Berlin, Germany: Springer-Verlag, 2002, pp. 254-262.
  • A. Fabrikant, E. Koutsoupias, and C. Papadimitriou, "Heuristically optimized trade-offs: A new paradigm for power laws in the Internet," in Automata, Languages and Programming: Proc. 29th Intl. Colloquium (ICALP 2002), P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz, and R. Conejo, Eds., Lecture Notes in Computer Science, Vol. 2380, Berlin, Germany: Springer-Verlag, 2002, pp. 110-122.
  • C. Papadimitriou, "Algorithms, games, and the Internet (Keynote Paper)," in Automata, Languages and Programming: Proc. 28th Intl. Colloquium (ICALP 2001), F. Orejas, P. G. Spirakis, and J. van Leeuwen, Eds., Lecture Notes in Computer Science, Vol. 2076, Berlin, Germany: Springer-Verlag, 2001, pp. 1-3.
  • G. Gottlob and C. Papadimitriou, "On the complexity of single-rule Datalog queries," in Logic for Programming and Automated Reasoning: Proc. 6th Intl Conf. (LPAR '99), H. Ganzinger, D. McAllester, and A. Voronkov, Eds., Lecture Notes in Computer Science, Vol. 1705, Berlin, Germany: Springer-Verlag, 1999, pp. 201-222.
  • 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.
  • X. Deng and C. Papadimitriou, "Decision-making by hierarchies of discordant agents," in Algorithms and Computation: Proc. 8th Intl. Symp. (ISAAC '97), H. W. Leong, H. Imai, and S. Jain, Eds., Lecture Notes in Computer Science, Vol. 1350, Berlin, Germany: Springer-Verlag, 1997, pp. 183-192.
  • C. Papadimitriou, "NP-completeness: A retrospective," in Automata, Languages and Programming: Proc. 24th Intl. Colloquium (ICALP '97), P. Degano, R. Gorrieri, and A. Marchetti-Spaccamela, Eds., Lecture Notes in Computer Science, Vol. 1256, Berlin, Germany: Springer-Verlag, 1997, pp. 2-6.
  • C. Papadimitriou, "Computational aspects of organization theory (Extended Abstract) (Invited Talk)," in Algorithms -- ESA '96: Proc. 4th Annual European Symp., J. Diaz and M. Serna, Eds., Lecture Notes in Computer Science, Vol. 1136, Berlin, Germany: Springer-Verlag, 1996, pp. 559-564.
  • E. Koutsoupias, C. Papadimitriou, and M. Yannakakis, "Searching a fixed graph," in Automata, Languages and Programming: Proc. 23rd Intl. Colloquium (ICALP 1996), F. Meyer auf der Heide and B. Monien, Eds., Lecture Notes in Computer Science, Vol. 1099, Berlin, Germany: Springer-Verlag, 1996, pp. 280-289.

Articles in journals or magazines

Articles in conference proceedings

  • C. Borgs, J. Chayes, N. Immorlica, A. T. Kalai, V. Mirrokni, and C. Papadimitriou, "The myth of the folk theorem," in Proc. 40th Annual ACM Symp. on Theory of Computing (STOC '08), New York, NY: The Association for Computing Machinery, Inc., 2008, pp. 365-372.
  • H. Lin, C. Amanatidis, M. Sideri, R. M. Karp, and C. Papadimitriou, "Linked decompositions of networks and the power of choice in Polya urns," in Proc. 19th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA '08), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2008, pp. 993-1002.
  • A. Fabrikant and C. Papadimitriou, "The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond," in Proc. 19th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA '08), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2008, pp. 844-853.
  • K. Daskalakis and C. Papadimitriou, "Computing equilibria in anonymous games," in Proc. 48th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2007), Los Alamitos, CA: IEEE Computer Society, 2007, pp. 83-93.
  • L. Popa, A. Rostamizadeh, R. M. Karp, C. Papadimitriou, and I. Stoica, "Balancing traffic load in wireless networks with curveball routing," in Proc. 8th ACM Intl. Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc '07), New York, NY: The Association for Computing Machinery, Inc., 2007, pp. 170-179.
  • K. Daskalakis, A. Mehta, and C. Papadimitriou, "Progress in approximate Nash equilibria," in Proc. 8th ACM Conf. on Electronic Commerce (EC '07), New York, NY: The Association for Computing Machinery, Inc., 2007, pp. 355-358.
  • M. Babaioff, R. Kleinberg, and C. Papadimitriou, "Congestion games with malicious players," in Proc. 8th ACM Conf. on Electronic Commerce (EC '07), New York, NY: The Association for Computing Machinery, Inc., 2007, pp. 103-112.
  • K. Daskalakis and C. Papadimitriou, "Computing pure Nash equilibria in graphical games via Markov random fields," in Proc. 7th ACM Conf. on Electronic Commerce (EC '06), J. Feigenbaum, J. Chuang, and D. Pennock, Eds., New York,NY: The Association for Computing Machinery, Inc., 2006, pp. 91-99.
  • K. Daskalakis, P. W. Goldbergt, and C. Papadimitriou, "The complexity of computing a Nash equilibrium," in Proc. 38th Annual ACM Symp. on Theory of Computing (STOC '06), New York, NY: The Association for Computing Machinery, Inc., 2006, pp. 71-78.
  • P. W. Goldberg and C. Papadimitriou, "Reducibility among equilibrium problems," in Proc. 38th Annual ACM Symp. on Theory of Computing (STOC '06), New York, NY: The Association for Computing Machinery, Inc., 2006, pp. 61-70.
  • G. Kouroupas, E. Koutsoupias, C. Papadimitriou, and M. Sideri, "An economic model of the Worldwide Web (Poster Session)," in Proc. 14th Intl. Conf. on World Wide Web (WWW 2005): Special Interest Tracks and Posters, New York, NY: The Association for Computing Machinery, Inc., 2005, pp. 934-935.
  • C. Papadimitriou, "Computing correlated equilibria in multi-player games," in Proc. 37th Annual ACM Symp. on Theory of Computing (STOC '05), New York, NY: The Association for Computing Machinery, Inc., 2005, pp. 49-56.
  • C. Papadimitriou and T. Roughgarden, "Computing equilibria in multi-player games," in Proc. 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA '05), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2005, pp. 82-91.
  • C. Papadimitriou and S. Safra, "The complexity of low-distortion embeddings between point sets," in Proc. 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA '05), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2005, pp. 112-118.
  • B. Chun, K. Chaudhuri, H. Wee, M. Barreno, C. Papadimitriou, and J. D. Kubiatowicz, "Selfish caching in distributed systems: A game-theoretic analysis," in Proc. 23 Annual ACM Symp. on Principles of Distributed Computing (PODC '04), New York, NY: The Association for Computing Machinery, Inc., 2004, pp. 21-30.
  • A. Fabrikant, C. Papadimitriou, and K. Talwar, "The complexity of pure Nash equilibria," in Proc. 36th Annual ACM Symp. on Theory of Computing (STOC '04), New York, NY: The Association for Computing Machinery, Inc., 2004, pp. 604-612.
  • M. Mihail, C. Papadimitriou, and A. Saberi, "On certain connectivity properties of the Internet topology," in Proc. 44th Annual IEEE Foundations of Computer Science (FOCS 2003), Los Alamitos, CA: IEEE Computer Society, 2003, pp. 28-35.
  • 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.
  • A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, and S. Shenker, "On a network creation game," in Proc. 22nd Annual Symp. on Principles of Distributed Computing (PODC '03), New York, NY: The Association for Computing Machinery, Inc., 2003, pp. 347-351.
  • C. Papadimitriou, "The new problems," in Proc. Paris C. Kanellakis Memorial Workshop on Principles of Computing and Knowledge (PCK50 2003), ACM International Conference Proceedings Series, Vol. 41, New York, NY: The Association for Computing Machinery, Inc., 2003, pp. 10-10.
  • A. Archer, C. Papadimitriou, K. Talwar, and E. Tardos, "An approximate truthful mechanism for combinatorial auctions with single parameter agents," in Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA '03), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2003, pp. 205-214.
  • N. R. Devanur, C. Papadimitriou, A. Saberi, and V. V. Vazirani, "Market equilibrium via a primal-dual-type algorithm," in Proc. 43rd Annual IEEE Symp. on Foundations of Computer Science (FOCS 2002), Los Alamitos, CA: IEEE Computer Society, 2002, pp. 389-395.
  • A. Akella, S. Seshan, R. M. Karp, S. Shenker, and C. Papadimitriou, "Selfish behavior and stability of the Internet: A game-theoretic analysis of TCP," in Proc. 2002 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '02), New York, NY: The Association for Computing Machinery, Inc., 2002, pp. 117-130.
  • J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, "A BGP-based mechanism for lowest-cost routing," in Proc. 21st ACM Annual Symp. on Principles of Distributed Computing (PODC '02), New York, NY: The Association for Computing Machinery, Inc., 2002, pp. 173-182.
  • X. Deng, C. Papadimitriou, and S. Safra, "On the complexity of equilibria," in Proc. 34th Annual ACM Symp. on Theory of Computing (STOC '02), New York, NY: The Association for Computing Machinery, Inc., 2002, pp. 67-71.
  • C. Papadimitriou, "Game theory and mathematical economics: A theoretical computer scientist's introduction," in Proc. 42nd IEEE Symp. on Foundations of Computer Science (FOCS 2001), Los Alamitos, CA: IEEE Computer Society, 2001, pp. 4-8.
  • J. Kleinberg, C. Papadimitriou, and P. Raghavan, "On the value of private information," in Proc. 8th Conf. on Theoretical Aspects of Rationality and Knowledge (TARK 2001), J. van Benthem, Ed., San Francisco, CA: Morgan Kaufmann Publishers, Inc., 2001, pp. 249-257.
  • C. Papadimitriou and M. Yannakakis, "Multiobjective query optimization," in Proc. 20th ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems (PODS 2001), New York, NY: The Association for Computing Machinery, Inc., 2001, pp. 52-59.
  • C. Papadimitriou and M. Yannakakis, "On the approximability of trade-offs and optimal access of Web sources," in Proc. 41st Annual Symp. on Foundations of Computer Science (FOCS 2000), Los Alamitos, CA: IEEE Computer Society, 2000, pp. 86-92.
  • R. M. Karp, E. Koutsoupias, C. Papadimitriou, and S. Shenker, "Optimization problems in congestion control," in Proc. 41st Annual Symp. on Foundations of Computer Science (FOCS 2000), Los Alamitos, CA: IEEE Computer Society, 2000, pp. 66-74.
  • J. Feigenbaum, C. Papadimitriou, and S. Shenker, "Sharing the cost of multicast transmissions," in Proc. 32nd Annual ACM Symp. on Theory of Computing (STOC '00), New York, NY: The Association for Computing Machinery, Inc., 2000, pp. 218-227.
  • J. Kleinberg, C. Papadimitriou, and P. Raghavan, "Auditing Boolean attributes," in Proc. 19th ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems (PODS 2000), New York, NY: The Association for Computing Machinery, Inc., 2000, pp. 86-91.
  • C. Papadimitriou and S. Vempala, "On the approximability of the traveling salesman problem," in Proc. 32nd Annual ACM Symp. on Theory of Computing (STOC '00), New York, NY: The Association for Computing Machinery, Inc., 2000, pp. 126-133.
  • C. Papadimitriou, H. Tamaki, P. Raghavan, and S. Vempala, "Latent semantic indexing: A probabilistic analysis," in Proc. 17th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (PODS 1998), New York, NY: The Association for Computing Machinery, Inc., 1998, pp. 159-168.
  • Z. Chen, M. Grigni, and C. Papadimitriou, "Planar map graphs," in Proc. 30th Annual ACM Symp. on Theory of Computing (STOC '98), New York, NY: The Association for Computing Machinery, Inc., 1998, pp. 514-523.
  • J. Kleinberg, C. Papadimitriou, and P. Raghavan, "Segmentation problems," in Proc. 30th Annual ACM Symp. on Theory of Computing (STOC '98), New York, NY: The Association for Computing Machinery, Inc., 1998, pp. 473-482.
  • P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni, and M. Yannakakis, "On the complexity of protein folding (Extended Abstract)," in Proc. 30th Annual ACM Symp. on Theory of Computing (STOC '98), New York, NY: The Association for Computing Machinery, Inc., 1998, pp. 597-603.
  • C. Papadimitriou and M. Yannakakis, "On the complexity of database queries (Extended Abstract)," in Proc. 16th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (PODS 1997), New York, NY: The Association for Computing Machinery, Inc., 1997, pp. 12-19.
  • J. M. Hellerstein, E. Koutsoupias, and C. Papadimitriou, "On the analysis of indexing schemes," in Proc. 16th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (PODS 1997), New York,NY: The Association for Computing Machinery, Inc., 1997, pp. 249-256.
  • 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.
  • L. M. Kirousis and C. Papadimitriou, "The complexity of recognizing polyhedral scenes," in Proc. 26th IEEE Annual Symp. on Foundations of Computer Science (FOCS 1985), Los Alamitos, CA: IEEE Computer Society, 1985, pp. 175-185.

Conference proceedings (edited)

Technical Reports

Patents

Talks or presentations

Ph.D. Theses