# 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

- N. R. Devanur, C. Papadimitriou, A. Saberi, and V. V. Vazirani, "Market equilibrium via a primal--dual algorithm for a convex program,"
*J. ACM*, vol. 55, no. 5, pp. Art. 22:1-18, Oct. 2008. - C. Papadimitriou and T. Roughgarden, "Computing correlated equilibria in multi-player games,"
*J. ACM*, vol. 55, no. 3, pp. Art. 14:1-29, July 2008. - A. W. J. Kolen, J. K. Lenstra, C. Papadimitriou, and F. C. R. Spieksma, "Interval scheduling: A survey,"
*Naval Research Logistics*, vol. 54, no. 5, pp. 530-543, Aug. 2007. - V. Koltun and C. Papadimitriou, "Approximately dominating representatives,"
*Theoretical Computer Science*, vol. 371, no. 3, pp. 148-154, March 2007. - Z. Chen, M. Grigni, and C. Papadimitriou, "Recognizing hole-free 4-map graphs in cubic time,"
*Algorithmica*, vol. 45, no. 2, pp. 227-262, June 2006. - M. Feldman, C. Papadimitriou, J. Chuang, and I. Stoica, "Free-riding and whitewashing in peer-to-peer systems,"
*IEEE J. Selected Areas in Communications*, vol. 24, no. 5, pp. 1010-1019, May 2006. - M. Mihal, C. Papadimitriou, and A. Saberi, "On certain connectivity properties of the Internet topology,"
*J. Computer and System Sciences: Special Issue on FOCS 2003*, vol. 72, no. 2, pp. 239-251, March 2006. - C. Papadimitriou and S. Vempala, "On the approximability of the traveling salesman problem,"
*Combinatorica*, vol. 26, no. 1, pp. 101-120, Feb. 2006. - K. Daskalakis and C. Papadimitriou, "Three-player games are hard,"
*Electronic Colloquium on Computational Complexity*, vol. 12, pp. Art. 139, 2005. - K. Daskalakis, P. W. Goldberg, and C. Papadimitriou, "The complexity of computing a Nash equilibrium,"
*Electronic Colloquium on Computational Complexity*, vol. 12, pp. Art. 115, 2005. - P. W. Goldberg and C. Papadimitriou, "Reducibility among equilibrium problems,"
*Electronic Colloquium on Computational Complexity*, vol. 12, pp. Art. 90, 2005. - C. Papadimitriou and D. Ratajczak, "On a conjecture related to geometric routing,"
*Theoretical Computer Science*, vol. 344, no. 1, pp. 3-14, Nov. 2005. - 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. - J. Kleinberg, C. Papadimitriou, and P. Raghavan, "Segmentation problems,"
*J. ACM*, vol. 51, no. 2, pp. 263-280, March 2004. - A. Archer, C. Papadimitriou, K. Talwar, and E. Tardos, "An approximate truthful mechanism for combinatorial auctions with single parameter agents,"
*Internet Mathematics*, vol. 1, no. 2, pp. 129-150, 2003. - X. Deng, C. Papadimitriou, and S. Safra, "On the complexity of price equilibria,"
*J. Computer and Systems Sciences*, vol. 67, no. 2, pp. 311-324, Sep. 2003. - 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. - G. Gottlob and C. Papadimitriou, "On the complexity of single-rule Datalog queries,"
*Information and Computation*, vol. 183, no. 1, pp. 104-122, May 2003. - R. M. Karp, S. Shenker, and C. Papadimitriou, "A simple algorithm for finding frequent elements in streams and bags,"
*ACM Trans. Database Systems*, vol. 28, no. 1, pp. 51-55, March 2003. - J. Kleinberg, C. Papadimitriou, and P. Raghavan, "Auditing Boolean attributes,"
*J. Computer and System Sciences*, vol. 66, no. 1, pp. 244-253, Feb. 2003. - E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, and U. Schoning, "A deterministic $ (2-2/(k+1))^n $ algorithm for k-SAT based local search,"
*Theoretical Computer Science*, vol. 289, no. 1, pp. 69-83, Oct. 2002. - 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,"
*ACM SIGCOMM Computer Communication Review: Proc. 2002 SIGCOMM Conf.*, vol. 32, no. 4, pp. 117-130, Oct. 2002. - Z. Chen, M. Grigni, and C. Papadimitriou, "Map graphs,"
*J. ACM*, vol. 49, no. 2, pp. 127-138, March 2002. - J. M. Hellerstein, E. Koutsoupias, D. P. Miranker, C. Papadimitriou, and V. Samoladas, "On a model of indexability and its bounds for range queries,"
*J. ACM*, vol. 49, no. 1, pp. 35-55, Jan. 2002. - P. Crescenzi, X. Deng, and C. Papadimitriou, "On approximating a scheduling problem,"
*J. Combinatorial Optimization*, vol. 5, no. 3, pp. 287-297, Sep. 2001. - 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. - V. D. Blondel, O. Bournez, P. Koiran, C. Papadimitriou, and J. N. Tsitsiklis, "Deciding stability and mortality of piecewise affine dynamical systems,"
*Theoretical Computer Science*, vol. 255, no. 1-2, pp. 687-696, March 2001. - M. Grigni, V. Mirelli, and C. Papadimitriou, "On the difficulty of designing good classifiers,"
*SIAM J. Computing*, vol. 30, no. 1, pp. 318-323, 2000. - E. Koutsoupias and C. Papadimitriou, "Beyond competitive analysis,"
*SIAM J. Computing*, vol. 30, no. 1, pp. 300-317, 2000. - K. A. Ross, Y. E. Ioannidis, A. Jhingran, and C. Papadimitriou, "Reminiscences on influential papers,"
*ACM SIGMOD Record*, vol. 29, no. 4, pp. 48-49, Dec. 2000. - R. Desper, F. Jiang, O. P. Kallioniemi, H. Moch, C. Papadimitriou, and A. A. Schaffer, "Distance-based reconstruction of tree models for oncogenesis,"
*J. Computational Biology*, vol. 7, no. 6, pp. 789-803, Dec. 2000. - 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. - R. Desper, F. Jiang, O. P. Kallioniemi, H. Moch, C. Papadimitriou, and A. A. Schaffer, "Inferring tree models for oncogenesis from comparative genome hybridization data,"
*J. Computational Biology*, vol. 6, no. 1, pp. 37-52, 1999. - C. Papadimitriou and M. Sideri, "On the Floyd-Warshall algorithm for logic programs,"
*J. Logic Programming*, vol. 41, no. 1, pp. 129-137, Oct. 1999. - C. Papadimitriou and M. Yannakakis, "On the complexity of database queries,"
*J. Computer and System Sciences*, vol. 58, no. 3, pp. 407-427, June 1999. - A. Condon, H. Edelsbrunner, E. A. Emerson, L. Fortnow, S. Haber, R. M. Karp, D. Leivant, R. Lipton, N. Lynch, I. Parberry, C. Papadimitriou, M. Rabin, A. Rosenberg, J. S. Royer, J. Savage, A. L. Selman, C. Smith, E. Tardos, and J. S. Vitter, "Challenges for theory of computing,"
*ACM SIGACT News*, vol. 30, no. 2, pp. 62-76, June 1999. - C. Papadimitriou and J. N. Tsitsiklis, "The complexity of optimal queuing network control,"
*Mathematics of Operations Research*, vol. 24, no. 2, pp. 293-305, May 1999. - C. Papadimitriou, D. Suciu, and V. Vianu, "Topological queries in spatial databases,"
*J. Computer and System Sciences*, vol. 58, no. 1, pp. 29-53, Feb. 1999. - G. Gogic, C. Papadimitriou, and M. Sideri, "Incremental recompilation of knowledge,"
*J. Artificial Intelligence Research*, vol. 8, pp. 23-27, 1998. - J. Kleinberg, C. Papadimitriou, and P. Raghavan, "A microeconomic view of data mining,"
*Data Mining and Knowledge Discovery*, vol. 2, no. 4, pp. 311-324, Dec. 1998. - S. Abiteboul, C. Papadimitriou, and V. Vianu, "Reflective relational machines,"
*Information and Computation*, vol. 143, no. 2, pp. 110-136, June 1998. - X. Deng, T. Kamada, and C. Papadimitriou, "How to learn an unknown environment. I. The rectilinear case,"
*J. ACM*, vol. 45, no. 2, pp. 215-245, March 1998. - A. V. Aho, D. S. Johnson, R. M. Karp, S. R. Kosaraju, C. C. McGeoch, C. Papadimitriou, and P. Pevzner, "Emerging opportunities for Theoretical Computer Science,"
*ACM SIGACT News*, vol. 28, no. 3, pp. 65-74, Sep. 1997. - Y. Dimopoulos, V. Magirou, and C. Papadimitriou, "On kernels, defaults and even graphs,"
*Annals of Mathematics and Artificial Intelligence*, vol. 20, no. 1-4, pp. 1-12, July 1997. - C. Papadimitriou and M. Yannakakis, "Tie-breaking semantics and structural totality,"
*J. Computer and System Sciences*, vol. 54, no. 1, pp. 46-80, Feb. 1997. - C. Papadimitriou and M. Yannakakis, "On limited nondeterminism and the complexity of the V-C dimension,"
*J. Computer and System Sciences*, vol. 53, no. 2, pp. 161-170, Oct. 1996. - C. Papadimitriou, O. Goldreich, A. Wigderson, A. A. Razborov, and M. Sipser, "The future of computational complexity theory: Part I (Guest Column),"
*ACM SIGACT News*, vol. 27, no. 3, pp. 6-12, Sep. 1996. - X. Deng and C. Papadimitriou, "Competitive distributed decision-making,"
*Algorithmica*, vol. 16, no. 2, pp. 133-150, Aug. 1996. - C. Papadimitriou and M. Sideri, "The bisection width of grid graphs,"
*Mathematical Systems Theory*, vol. 29, no. 2, pp. 97-110, April 1996. - E. Koutsoupias and C. Papadimitriou, "The 2-evader problem,"
*Information Processing Letters*, vol. 57, no. 5, pp. 249-252, March 1996. - C. Papadimitriou, "Database metatheory: Asking the big queries,"
*ACM SIGACT News*, vol. 26, no. 3, pp. 13-30, Sep. 1995. - E. Koutsoupias and C. Papadimitriou, "On the k-server conjecture,"
*J. ACM*, vol. 42, no. 5, pp. 971-983, Sep. 1995. - P. Crescenzi and C. Papadimitriou, "Reversible simulation of space-bounded computations,"
*Theoretical Computer Science*, vol. 143, no. 1, pp. 159-165, July 1995. - C. Papadimitriou, S. Ramanathan, P. V. Rangan, and S. SampathKumar, "Multimedia information caching for personalized video-on-demand,"
*Computer Communications: Issue on Multimedia Storage Servers*, vol. 18, no. 3, pp. 204-216, March 1995. - C. Papadimitriou and M. Sideri, "Default theories that always have extensions,"
*Artificial Intelligence*, vol. 69, no. 1-2, pp. 347-357, Sep. 1994. - E. Dahlhaus, D. S. Johnson, C. Papadimitriou, P. D. Seymour, and M. Yannakakis, "The complexity of multiterminal cuts,"
*SIAM J. Computing*, vol. 23, no. 4, pp. 864-894, Aug. 1994. - C. Papadimitriou, "On the complexity of the parity argument and other inefficient proofs of existence,"
*J. Computer and System Sciences*, vol. 48, no. 3, pp. 498-532, June 1994. - C. Papadimitriou, "On the complexity of the parity argument and other inefficient proofs of existence,"
*J. Computer and System Sciences*, vol. 48, no. 3, pp. 498-532, June 1994. - C. Papadimitriou, V. Rangan, and M. Sideri, "Designing secure communication protocols from trust specifications,"
*Algorithmica*, vol. 11, no. 5, pp. 485-499, May 1994. - X. Deng and C. Papadimitriou, "On the complexity of cooperative solution concepts,"
*Mathematics of Operations Research*, vol. 19, no. 2, pp. 257-266, May 1994. - F. Afrati, C. Papadimitriou, F. Afrati, and C. Papadimitriou, "The parallel complexity of simple logic programs,"
*J. ACM*, vol. 40, no. 4, pp. 891-916, Sep. 1993. - C. Papadimitriou, P. Serafini, and M. Yannakakis, "Computing the throughput of a network with dedicated lines,"
*Discrete Applied Mathematics*, vol. 42, no. 2-3, pp. 271-278, April 1993. - C. Papadimitriou and M. Yannakakis, "The traveling salesman problem with distances one and two,"
*Mathematics of Operations Research*, vol. 18, no. 1, pp. 1-11, Feb. 1993. - E. Koutsoupias, C. Papadimitriou, and M. Sideri, "On the optimal bisection of a polygon,"
*ORSA J. on Computing*, vol. 4, no. 4, pp. 435-438, 1992. - E. Koutsoupias and C. Papadimitriou, "On the greedy algorithm for satisfiability,"
*Information Processing Letters*, vol. 43, no. 1, pp. 53-55, Aug. 1992. - C. Papadimitriou, "The complexity of the Lin-Kernighan heuristic for the traveling salesman problem,"
*SIAM J. on Computing*, vol. 21, no. 3, pp. 450-465, June 1992. - C. Papadimitriou, "On platers with a bounded number of states,"
*Games and Economic Behavior*, vol. 4, no. 1, pp. 122-131, Jan. 1992. - C. Papadimitriou and M. Yannakakis, "Optimization, approximation and complexity classes,"
*J. Computer and System Sciences*, vol. 43, no. 3, pp. 425-440, Dec. 1991. - S. R. Buss, C. Papadimitriou, and J. N. Tsitsiklis, "On the predictability of coupled automata: An allegory about chaos,"
*Complex Systems*, vol. 5, no. 5, pp. 525-539, Oct. 1991. [abstract] - P. G. Kolaitis and C. Papadimitriou, "Why not negation by fixpoint?,"
*J. Computer and System Sciences*, vol. 43, no. 1, pp. 125-144, Aug. 1991. - C. Papadimitriou and M. Yannakakis, "Shortest paths without a map,"
*Theoretical Computer Science*, vol. 84, no. 1, pp. 127-150, July 1991. - N. Megiddo and C. Papadimitriou, "On total functions, existence theorems and computational complexity,"
*Theoretical Computer Science*, vol. 81, no. 2, pp. 317-324, April 1991. - E. M. Arkin, C. Papadimitriou, and M. Yannakakis, "Modularity of cycles and paths in graphs,"
*J. ACM*, vol. 38, no. 2, pp. 255-274, April 1991. - J. S. B. Mitchell and C. Papadimitriou, "The weighted region problem: Finding shortest paths through a weighted planar subdivision,"
*J. ACM*, vol. 38, no. 1, pp. 18-73, Jan. 1991. - J. G. Kollias, Y. Manolopoulos, and C. Papadimitriou, "The optimum execution order of queries in linear storage,"
*Information Processing Letters*, vol. 36, no. 3, pp. 141-145, Nov. 1990. - C. Papadimitriou and M. Yannakakis, "Towards an architecture-independent analysis of parallel algorithms,"
*SIAM J. Computing*, vol. 19, no. 2, pp. 322-328, April 1990. - X. Markenscoff, L. Ni, and C. Papadimitriou, "The geometry of grasping,"
*Intl. J. Robotics Research*, vol. 9, no. 1, pp. 61-74, Feb. 1990. - P. G. Kolaitis and C. Papadimitriou, "Some computational aspects of circumscription,"
*J. ACM*, vol. 37, no. 1, pp. 1-14, Jan. 1990. - L. M. Kirousis and C. Papadimitriou, "The complexity of recognizing polyhedral scenes,"
*J. Computer and System Sciences*, vol. 37, no. 1, pp. 14-38, Aug. 1988. - C. Papadimitriou, "The serializability of concurrent database updates,"
*J. ACM*, vol. 26, no. 4, pp. 631-653, Oct. 1979. - W. H. Gates and C. Papadimitriou, "Bounds for sorting by prefix reversal,"
*Discrete Mathematics*, vol. 27, no. 1, pp. 47-57, July 1979.

## 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)

- C. Papadimitriou and S. Zhang, Eds.,
*Internet and Network Ecomonics: Proceedings of the 4th International Workshop (WINE 2008)*, Lecture Notes in Computer Science, Vol. 5385, Berlin, Germany: Springer-Verlag, 2008.

## Technical Reports

- G. Cheung, S. McCanne, and C. Papadimitriou, "Software Synthesis of Variable-length Code Decoder using a Mixture of Programmed Logic and Table Lookups," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-99-1040, Feb. 1999. [abstract]

## Patents

- C. Papadimitriou and P. V. Rangan, "System and method for selecting cache server based on transmission and storage factors for efficient delivery of multimedia information in a hierarchical network of servers," U.S. Patent 5,592,626. Jan. 1997.

## Talks or presentations

- C. Papadimitriou, "Some Recent Results in Algorithmic Game Theory (Invited Tutorial Session Talk)," presented at 4th International Workshop on Internet and Network Economics, Shanghai, China, Dec. 2008.
- C. Papadimitriou, "The Search for Equilibrium Concepts (Invited Talk)," in
*Algorithmic Game Theory: Proc. 1st Intl. Symp. (SAGT 2008)*, B. Monien and U. Schroeder, Eds., presented at 1st International Symposium on Algorithmic Game Theory (SAGT 2008), Paderborn, Germany, May 2008. - C. Papadimitriou, "The Computation of Equilibria (Plenary Talk)," presented at 3rd International Workshop on the Internet and Network Economics (WINE 2007), San Diego, CA, Dec. 2007.
- C. Papadimitriou, "Nash Equilibria: Where We Stand (Invited Lecture)," presented at 15th Annual European Symposium on Algorithms (ESA 2007), Eilat, Israel, Nov. 2007.
- C. Papadimitriou, "Recent Developments in Equilibria Algorithms (Invited Talk)," presented at 1st International Workshop on the Internet and Network Economics (WINE 2005), Hong Kong, China, Dec. 2005.
- C. Papadimitriou, "Games Other People Play (Invited Lecture)," presented at 16th International Conference on Concurrency Theory (CONCUR 2005), San Francisco, CA, Aug. 2005.
- C. Papadimitriou, "Algorithmic Problems in Ad Hoc Networks (Invited Talk)," presented at 1st IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS 2005), Marina del Rey, CA, June 2005.
- C. Papadimitriou, "The Interaction between Algorithms and Game Theory (Keynote Talk)," presented at 4th International Workshop on Experimental and Efficient Algorithms (WEA 2005), Santorini Island, Greece, May 2005.
- C. Papadimitriou, "Networks and Games (Keynote Address)," presented at 11th International Conference on High Performance Computing (HiPC 2004), Bangalore, India, Dec. 2004.
- C. Papadimitriou, "Games and Networks (Invited Lecture)," presented at 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), Malmo, Sweden, Aug. 2003.
- C. Papadimitriou, "Mythematics: Storytelling in the Teaching of Computer Science and Mathematics (Keynote Address)," presented at 8th Annual Conference on Innovation and Technology in Computer Science Education, Thessaloniki, Greece, June 2003.
- C. Papadimitriou, "Learning the Internet (Keynote Lecture)," presented at 15th Annual Conference on Computational Learning Theory (COLT 2002), Sydney, Australia, July 2002.
- C. Papadimitriou, "The Joy of Theory (Invited Talk)," presented at 34th Annual ACM Symposium on Theory of Computing (STOC '02), Montreal, Quebec, Canada, May 2002. [abstract]
- C. Papadimitriou, "Understanding the Internet (Invited Talk)," presented at 2nd Hellenic Conference on AI (SETN 2002), Thessaloniki, Greece, April 2002. [abstract]
- C. Papadimitriou, "The Internet, the Web, and Algorithms (Invited Talk)," presented at 5th Latin American Symposium (LATIN 2002), Cancun, Mexico, April 2002.
- C. Papadimitriou, "Algorithms, Games and the Internet (Invited Plenary Talk)," presented at 33rd Annual ACM Symp. on Theory of Computing (STOC '01), Crete, Greece, July 2001.
- C. Papadimitriou, "Algorithmic Problems Related to the Internet," presented at The 2001 Milner Lecture, Edinburgh, Scotland, UK, May 2001.
- C. Papadimitriou, "Game Theory, Algorithms, and the Internet (Invited Presentation)," presented at 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01), Washington, DC, Jan. 2001. [abstract]
- C. Papadimitriou, "On Certain Rigorous Approaches to Data Mining (Invited Talk)," presented at 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2000), Boston, MA, Aug. 2000.
- C. Papadimitriou, "Theoretical Problems Related to the Internet (Invited Keynote Speech)," presented at 6th Annual International Conference on Computing and Combinatorics (COCOON 2000), Sydney, Australia, July 2000.

## Ph.D. Theses

- A. A. Poggio, D. A. Patterson, A. Arkin, B. Mishler, and C. Papadimitriou, "The Path of the Blind Watchmaker: A Model of Evolution," EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2011-76, June 2011. [abstract]