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]