Christos H. Papadimitriou
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
177
Venues
42
Active years
1976–2025
Best venue rank
A*
Where they publish
- A*FOCS32 papers
- A*STOC25 papers
- A*PODS20 papers
- A*ICALP15 papers
- A*SODA13 papers
- A*PODC7 papers
- A*COLT6 papers
- BSAGT5 papers
- BISAAC4 papers
- A*SIGMOD3 papers
- A*AAAI3 papers
- AESA3 papers
- AICDT3 papers
- NationalCOCOON3 papers
- BALT2 papers
- A*EC2 papers
- ASTACS2 papers
- CCIAC2 papers
- A*WWW2 papers
- BLATIN2 papers
- A*IJCAI2 papers
- A*ACL1 paper
- BAFT1 paper
- BFMCAD1 paper
- BIPCO1 paper
- CWAW1 paper
- BMOBIHOC1 paper
- BCONCUR1 paper
- BDCOSS1 paper
- CAlgosensors1 paper
- NationalHiPC1 paper
- BFCT1 paper
- BITiCSE1 paper
- A*MOBICOM1 paper
- A*SIGCOMM1 paper
- A*KDD1 paper
- BDCC1 paper
- BLPAR1 paper
- BRECOMB1 paper
- BWADS1 paper
- A*CAV1 paper
- A*LICS1 paper
Papers
177 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2025 | SIGMOD | How to Build A Brain. | Christos H. Papadimitriou |
| 2024 | ALT | Computation with Sequences of Assemblies in a Model of the Brain. | Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala |
| 2024 | ALT | The complexity of non-stationary reinforcement learning. | Binghui Peng, Christos H. Papadimitriou |
| 2024 | COLT | Online Stackelberg Optimization via Nonlinear Control. | William Brown, Christos H. Papadimitriou, Tim Roughgarden |
| 2024 | SAGT | Swim till You Sink: Computing the Limit of a Game. | Rashida Hakim, Jason Milionis, Christos H. Papadimitriou, Georgios Piliouras |
| 2022 | AAAI | Planning with Biological Neurons and Synapses. | Francesco d'Amore, Daniel Mitropolsky, Pierluigi Crescenzi, Emanuele Natale, Christos H. Papadimitriou |
| 2022 | COLT | Assemblies of neurons learn to classify well-separated distributions. | Max Dabagia, Santosh S. Vempala, Christos H. Papadimitriou |
| 2022 | FOCS | Memory Bounds for Continual Learning. | Xi Chen, Christos H. Papadimitriou, Binghui Peng |
| 2021 | ACL | Self-Attention Networks Can Process Bounded Hierarchical Languages. | Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, Karthik Narasimhan |
| 2019 | AFT | An Axiomatic Approach to Block Rewards. | Xi Chen, Christos H. Papadimitriou, Tim Roughgarden |
| 2019 | EC | Optimal Strategies of Blotto Games: Beyond Convexity. | Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin |
| 2019 | EC | Energy Equilibria in Proof-of-Work Mining. | Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Christos H. Papadimitriou |
| 2019 | STACS | Wealth Inequality and the Price of Anarchy. | Kurtulus Gemici, Elias Koutsoupias, Barnab Monnot, Christos H. Papadimitriou, Georgios Piliouras |
| 2018 | SODA | From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games. | Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark |
| 2018 | SODA | Cycles in Adversarial Regularized Learning. | Panayotis Mertikopoulos, Christos H. Papadimitriou, Georgios Piliouras |
| 2017 | CIAC | Stathis Zachos at 70! | Eleni Bakali, Panagiotis Cheilaris, Dimitris Fotakis, Martin Frer, Costas D. Koutras, Euripides Markou, Christos Nomikos, Aris Pagourtzis, Christos H. Papadimitriou, Nikolaos S. Papaspyrou, Katerina Potika |
| 2017 | CIAC | TFNP: An Update. | Paul W. Goldberg, Christos H. Papadimitriou |
| 2016 | COLT | Cortical Computation via Iterative Constructions. | Christos H. Papadimitriou, Samantha Petti, Santosh S. Vempala |
| 2016 | FMCAD | Understanding evolution through algorithms. | Christos H. Papadimitriou |
| 2016 | SODA | Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. | Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer |
| 2016 | SODA | On the Complexity of Dynamic Mechanism Design. | Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein |
| 2015 | COLT | Optimum Statistical Estimation with Strategic Data Sources. | Yang Cai, Constantinos Daskalakis, Christos H. Papadimitriou |
| 2015 | COLT | Cortical Learning via Prediction. | Christos H. Papadimitriou, Santosh S. Vempala |
| 2015 | PODC | Cortical Computation. | Christos H. Papadimitriou, Santosh S. Vempala |
| 2015 | SAGT | The Web Graph as an Equilibrium. | Georgios Kouroupas, Evangelos Markakis, Christos H. Papadimitriou, Vasileios Rigas, Martha Sideri |
| 2014 | FOCS | Satisfiability and Evolution. | Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan |
| 2014 | IPCO | On Simplex Pivoting Rules and Complexity Theory. | Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein |
| 2013 | PODS | Learning and verifying quantified boolean queries by example. | Azza Abouzied, Dana Angluin, Christos H. Papadimitriou, Joseph M. Hellerstein, Avi Silberschatz |
| 2012 | ICALP | Efficiency-Revenue Trade-Offs in Auctions. | Ilias Diakonikolas, Christos H. Papadimitriou, George Pierrakos, Yaron Singer |
| 2011 | FOCS | The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. | Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani |
| 2011 | WWW | Games, algorithms, and the Internet. | Christos H. Papadimitriou |
| 2011 | SODA | Continuous Local Search. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 2011 | STOC | On optimal single-item auctions. | Christos H. Papadimitriou, George Pierrakos |
| 2011 | WAW | Modeling Social Networks through User Background and Behavior. | Ilias Foudalis, Kamal Jain, Christos H. Papadimitriou, Martha Sideri |
| 2010 | SODA | Inapproximability for VCG-Based Combinatorial Auctions. | David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans |
| 2010 | SAGT | On Learning Algorithms for Nash Equilibria. | Constantinos Daskalakis, Rafael M. Frongillo, Christos H. Papadimitriou, George Pierrakos, Gregory Valiant |
| 2010 | SAGT | When the Players Are Not Expectation Maximizers. | Amos Fiat, Christos H. Papadimitriou |
| 2009 | ICALP | On a Network Generalization of the Minmax Theorem. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 2009 | ICALP | Algorithmic Game Theory: A Snapshot. | Christos H. Papadimitriou |
| 2009 | PODS | The ACM PODS Alberto O. Mendelzon test-of-time-award 2009. | Catriel Beeri, Phokion G. Kolaitis, Christos H. Papadimitriou |
| 2009 | STOC | On oblivious PTAS's for nash equilibrium. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 2008 | FOCS | Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 2008 | FOCS | On the Hardness of Being Truthful. | Christos H. Papadimitriou, Michael Schapira, Yaron Singer |
| 2008 | ISAAC | On the Complexity of Reconfiguration Problems. | Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno |
| 2008 | SODA | The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. | Alex Fabrikant, Christos H. Papadimitriou |
| 2008 | SODA | Linked decompositions of networks and the power of choice in Polya urns. | Henry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou |
| 2008 | STOC | The myth of the folk theorem. | Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou |
| 2008 | SAGT | The Search for Equilibrium Concepts. | Christos H. Papadimitriou |
| 2007 | ESA | Nash Equilibria: Where We Stand. | Christos H. Papadimitriou |
| 2007 | FOCS | Computing Equilibria in Anonymous Games. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 2007 | MOBIHOC | Balancing traffic load in wireless networks with curveball routing. | Lucian Popa, Afshin Rostamizadeh, Richard M. Karp, Christos H. Papadimitriou, Ion Stoica |
| 2006 | ICALP | The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. | Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou |
| 2006 | ICALP | The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. | Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou |
| 2006 | STOC | The complexity of computing a Nash equilibrium. | Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou |
| 2006 | STOC | Reducibility among equilibrium problems. | Paul W. Goldberg, Christos H. Papadimitriou |
| 2005 | CONCUR | Games Other People Play. | Christos H. Papadimitriou |
| 2005 | DCOSS | Algorithmic Problems in Ad Hoc Networks. | Christos H. Papadimitriou |
| 2005 | ESA | The Complexity of Games on Highly Regular Graphs. | Konstantinos Daskalakis, Christos H. Papadimitriou |
| 2005 | ICDT | Approximately Dominating Representatives. | Vladlen Koltun, Christos H. Papadimitriou |
| 2005 | WWW | An economic model of the worldwide web. | Georgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri |
| 2005 | SODA | Computing equilibria in multi-player games. | Christos H. Papadimitriou, Tim Roughgarden |
| 2005 | SODA | The complexity of low-distortion embeddings between point sets. | Christos H. Papadimitriou, Shmuel Safra |
| 2005 | STOC | Computing correlated equilibria in multi-player games. | Christos H. Papadimitriou |
| 2004 | Algosensors | On a Conjecture Related to Geometric Routing. | Christos H. Papadimitriou, David Ratajczak |
| 2004 | HiPC | Networks and Games. | Christos H. Papadimitriou |
| 2004 | LATIN | Global Synchronization in Sensornets. | Jeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker |
| 2004 | PODC | Selfish caching in distributed systems: a game-theoretic analysis. | Byung-Gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos H. Papadimitriou, John Kubiatowicz |
| 2004 | STOC | The complexity of pure Nash equilibria. | Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar |
| 2003 | FCT | Games and Networks. | Christos H. Papadimitriou |
| 2003 | FOCS | On Certain Connectivity Properties of the Internet Topology. | Milena Mihail, Christos H. Papadimitriou, Amin Saberi |
| 2003 | ITiCSE | Untitled record | Christos H. Papadimitriou |
| 2003 | MOBICOM | Geographic routing without location information. | Ananth Rao, Christos H. Papadimitriou, Scott Shenker, Ion Stoica |
| 2003 | PODC | On a network creation game. | Alex Fabrikant, Ankur Luthra, Elitza N. Maneva, Christos H. Papadimitriou, Scott Shenker |
| 2003 | SODA | An approximate truthful mechanism for combinatorial auctions with single parameter agents. | Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, va Tardos |
| 2002 | COLT | Learning the Internet. | Christos H. Papadimitriou |
| 2002 | FOCS | Market Equilibrium via a Primal-Dual-Type Algorithm. | Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani |
| 2002 | ICALP | Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. | Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou |
| 2002 | LATIN | The Internet, the Web, and Algorithms. | Christos H. Papadimitriou |
| 2002 | PODC | A BGP-based mechanism for lowest-cost routing. | Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker |
| 2002 | STOC | On the complexity of equilibria. | Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra |
| 2002 | STOC | The Joy of Theory. | Christos H. Papadimitriou |
| 2002 | SIGCOMM | Selfish behavior and stability of the internet: a game-theoretic analysis of TCP. | Aditya Akella, Srinivasan Seshan, Richard M. Karp, Scott Shenker, Christos H. Papadimitriou |
| 2001 | FOCS | Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. | Christos H. Papadimitriou |
| 2001 | ICALP | Algorithms, Games, and the Internet. | Christos H. Papadimitriou |
| 2001 | PODS | Multiobjective Query Optimization. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 2001 | SODA | Game theory, algorithms, and the Internet. | Christos H. Papadimitriou |
| 2001 | STOC | Algorithms, games, and the internet. | Christos H. Papadimitriou |
| 2000 | COCOON | Theoretical Problems Related to the Internet. | Christos H. Papadimitriou |
| 2000 | FOCS | Optimization Problems in Congestion Control. | Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker |
| 2000 | FOCS | On the Approximability of Trade-offs and Optimal Access of Web Sources. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 2000 | KDD | On certain rigorous approaches to data mining (invited talk, abstract only). | Christos H. Papadimitriou |
| 2000 | PODS | Auditing Boolean Attributes. | Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan |
| 2000 | STOC | Sharing the cost of muliticast transmissions (preliminary version). | Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker |
| 2000 | STOC | On the approximability of the traveling salesman problem (extended abstract). | Christos H. Papadimitriou, Santosh S. Vempala |
| 1999 | DCC | Software Synthesis of Variable-length Code Decoder Using a Mixture of Programmed Logic and Table Lookups. | Gene Cheung, Steven McCanne, Christos H. Papadimitriou |
| 1999 | FOCS | Algorithmic Aspects of Protein Structure Similarity. | Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou |
| 1999 | ICDT | Novel Computational Approaches to Information Retrieval and Data Mining (Abstract). | Christos H. Papadimitriou |
| 1999 | LPAR | On the Complexity of Single-Rule Datalog Queries. | Georg Gottlob, Christos H. Papadimitriou |
| 1999 | STACS | Worst-case Equilibria. | Elias Koutsoupias, Christos H. Papadimitriou |
| 1998 | COCOON | Algorithmic Approaches to Information Retrieval and Data Mining (Abstract). | Christos H. Papadimitriou |
| 1998 | PODS | Latent Semantic Indexing: A Probabilistic Analysis. | Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh S. Vempala |
| 1998 | RECOMB | On the complexity of protein folding (abstract). | Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis |
| 1998 | STOC | Planar Map Graphs. | Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou |
| 1998 | STOC | On the Complexity of Protein Folding (Extended Abstract). | Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis |
| 1998 | STOC | Segmentation Problems. | Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan |
| 1997 | ICALP | NP-Completeness: A Retrospective. | Christos H. Papadimitriou |
| 1997 | ISAAC | Decision-Making by Hierarchies of Discordant Agents. | Xiaotie Deng, Christos H. Papadimitriou |
| 1997 | PODS | On the Analysis of Indexing Schemes. | Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou |
| 1997 | PODS | On the Complexity of Database Queries. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1997 | WADS | Panarity, Revisited (Extended Abstract). | Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou |
| 1996 | COCOON | On the Difficulty of Designing Good Classifiers. | Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou |
| 1996 | ESA | Computational Aspacts of Organization Theory (Extended Abstract). | Christos H. Papadimitriou |
| 1996 | ICALP | Searching a Fixed Graph. | Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis |
| 1996 | PODS | In Memoriam: Paris C. Kanellakis. | Serge Abiteboul, Gabriel M. Kuper, Christos H. Papadimitriou, Moshe Y. Vardi |
| 1996 | PODS | Topological Queries in Spatial Databases. | Christos H. Papadimitriou, Dan Suciu, Victor Vianu |
| 1995 | FOCS | An Approximation Scheme for Planar Graph TSP. | Michelangelo Grigni, Elias Koutsoupias, Christos H. Papadimitriou |
| 1995 | IJCAI | The Comparative Linguistics of Knowledge Representation. | Goran Gogic, Henry A. Kautz, Christos H. Papadimitriou, Bart Selman |
| 1995 | IJCAI | Topological Inference. | Michelangelo Grigni, Dimitris Papadias, Christos H. Papadimitriou |
| 1995 | ISAAC | Optimal Information Delivery. | Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan |
| 1995 | PODS | Database Metatheory: Asking the Big Queries. | Christos H. Papadimitriou |
| 1994 | AAAI | Incremental Recompilation of Knowledge. | Goran Gogic, Christos H. Papadimitriou, Martha Sideri |
| 1994 | CAV | On the Random Walk Method for Protocol Testing. | Milena Mihail, Christos H. Papadimitriou |
| 1994 | FOCS | Beyond Competitive Analysis | Elias Koutsoupias, Christos H. Papadimitriou |
| 1994 | FOCS | Motion Planning on a Graph (Extended Abstract) | Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki |
| 1994 | LICS | The Power of Reflective Relational Machines | Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu |
| 1994 | STOC | On the | Elias Koutsoupias, Christos H. Papadimitriou |
| 1994 | STOC | On complexity as bounded rationality (extended abstract). | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1993 | ISAAC | On Horn Envelopes and Hypergraph Transversals. | Dimitris J. Kavvadias, Christos H. Papadimitriou, Martha Sideri |
| 1993 | STOC | Linear programming without the matrix. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1992 | ICDT | On Finding Extensions of Default Theories. | Christos H. Papadimitriou, Martha Sideri |
| 1992 | PODS | Tie-Breaking Semantics and Structural Totality. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1992 | STOC | The Complexity of Multiway Cuts (Extended Abstract) | Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis |
| 1991 | FOCS | How to Learn an Unknown Environment (Extended Abstract) | Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou |
| 1991 | FOCS | On Selecting a Satisfying Truth Assignment (Extended Abstract) | Christos H. Papadimitriou |
| 1991 | PODC | Optimal Coteries. | Christos H. Papadimitriou, Martha Sideri |
| 1991 | PODC | On the Value of Information in Distributed Decision-Making (Extended Abstract). | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1990 | FOCS | On the Predictability of Coupled Automata: An Allegory about Chaos | Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis |
| 1990 | FOCS | Exploring an Unknown Graph (Extended Abstract) | Xiaotie Deng, Christos H. Papadimitriou |
| 1990 | FOCS | On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract) | Christos H. Papadimitriou |
| 1990 | SODA | The Bisection Width of Grid Graphs. | Christos H. Papadimitriou, Martha Sideri |
| 1990 | STOC | On the Complexity of Local Search (Extended Abstract) | Christos H. Papadimitriou, Alejandro A. Schffer, Mihalis Yannakakis |
| 1989 | ICALP | Shortest Paths Without a Map. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | AAAI | Some Computational Aspects of Circumscription. | Phokion G. Kolaitis, Christos H. Papadimitriou |
| 1988 | PODS | Why Not Negation by Fixpoint? | Phokion G. Kolaitis, Christos H. Papadimitriou |
| 1988 | STOC | Optimization, Approximation, and Complexity Classes (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | STOC | Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1987 | PODS | The Parallel Complexity of Simple Chain Queries. | Foto N. Afrati, Christos H. Papadimitriou |
| 1986 | PODC | The Synthesis of Communication Protocols. | Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou |
| 1986 | PODS | Convergence of Sideways Query Evaluation. | Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman |
| 1985 | FOCS | How Easy Is Local Search? (Extended Abstract) | David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis |
| 1985 | FOCS | The Complexity of Recognizing Polyhedral Scenes (Extended Abstract) | Lefteris M. Kirousis, Christos H. Papadimitriou |
| 1985 | FOCS | The Complexity of Facets Resolved | Christos H. Papadimitriou, David Wolfe |
| 1985 | PODS | Algorithmic Aspects of Multiversion Concurrency Control. | Thanasis Hadzilacos, Christos H. Papadimitriou |
| 1985 | PODS | The Complexity of Reliable Concurrency Control. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1984 | FOCS | A Communication-Time Tradeoff | Christos H. Papadimitriou, Jeffrey D. Ullman |
| 1984 | ICALP | The Complexity of Cubical Graphs (Extended Abstract). | Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou |
| 1983 | FOCS | Games Against Nature (Extended Abstract) | Christos H. Papadimitriou |
| 1983 | ICALP | Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract). | Mihalis Yannakakis, Paris C. Kanellakis, Stavros S. Cosmadakis, Christos H. Papadimitriou |
| 1983 | PODS | Updates of Relational Views. | Stavros S. Cosmadakis, Christos H. Papadimitriou |
| 1982 | FOCS | On the Complexity of Unique Solutions | Christos H. Papadimitriou |
| 1982 | PODS | Inclusion Dependencies and Their Interaction with Functional Dependencies. | Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou |
| 1982 | PODS | Is Distributed Locking Harder? | Paris C. Kanellakis, Christos H. Papadimitriou |
| 1982 | PODS | On Concurrency Control by Multiple Versions. | Christos H. Papadimitriou, Paris C. Kanellakis |
| 1982 | STOC | Communication Complexity | Christos H. Papadimitriou, Michael Sipser |
| 1982 | STOC | The Complexity of Facets (and Some Facets of Complexity) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1981 | FOCS | The Complexity of Distributed Concurrency Control | Paris C. Kanellakis, Christos H. Papadimitriou |
| 1981 | FOCS | The Complexity of Searching a Graph (Preliminary Version) | Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou |
| 1981 | FOCS | Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1981 | SIGMOD | On the Power of Locking. | Christos H. Papadimitriou |
| 1980 | FOCS | On Linear Characterizations of Combinatorial Optimization Problems | Richard M. Karp, Christos H. Papadimitriou |
| 1980 | FOCS | Algebraic Dependencies (Extended Abstract) | Mihalis Yannakakis, Christos H. Papadimitriou |
| 1980 | ICALP | Symmetric Space-Bounded Computation (Extended Abstract). | Harry R. Lewis, Christos H. Papadimitriou |
| 1980 | ICALP | A Worst-Case Analysis of Nearest Neighbor Searching by Projection. | Christos H. Papadimitriou, Jon Louis Bentley |
| 1979 | FOCS | Locking Policies: Safety and Freedom from Deadlock | Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung |
| 1979 | ICALP | The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1979 | SIGMOD | An Optimality Theory of Concurrency Control for Databases. | H. T. Kung, Christos H. Papadimitriou |
| 1976 | STOC | Some Complexity Results for the Traveling Salesman Problem | Christos H. Papadimitriou, Kenneth Steiglitz |