| |
 |      |
                                              |
Note: Links lead to the DBLP on the Web. Christos H. Papadimitriou Jeremy Elson , Richard M. Karp , Christos H. Papadimitriou, Scott Shenker : Global Synchronization in Sensornets. LATIN 2004 : 609-624 Jon M. Kleinberg , Christos H. Papadimitriou, Prabhakar Raghavan : Segmentation problems. J. ACM 51 (2): 263-280 (2004) Christos H. Papadimitriou: Games and Networks. FCT 2003 : 157 Milena Mihail , Christos H. Papadimitriou, Amin Saberi : On Certain Connectivity Properties of the Internet Topology. FOCS 2003 : 28-35 Ananth Rao , Christos H. Papadimitriou, Scott Shenker , Ion Stoica : Geographic routing without location information. MOBICOM 2003 : 96-108 Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou, Scott Shenker : On a network creation game. PODC 2003 : 347-351 Aaron Archer , Christos H. Papadimitriou, Kunal Talwar , Éva Tardos : An approximate truthful mechanism for combinatorial auctions with single parameter agents. SODA 2003 : 205-214 Richard M. Karp , Scott Shenker , Christos H. Papadimitriou: A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 28 : 51-55 (2003) Georg Gottlob , Christos H. Papadimitriou: On the complexity of single-rule datalog queries. Inf. Comput. 183 (1): 104-122 (2003) Jon M. Kleinberg , Christos H. Papadimitriou, Prabhakar Raghavan : Auditing Boolean attributes. J. Comput. Syst. Sci. 66 (1): 244-253 (2003) Xiaotie Deng , Christos H. Papadimitriou, Shmuel Safra : On the complexity of price equilibria. J. Comput. Syst. Sci. 67 (2): 311-324 (2003) Christos H. Papadimitriou: Learning the Internet. COLT 2002 : 396 Nikhil R. Devanur , Christos H. Papadimitriou, Amin Saberi , Vijay V. Vazirani : Market Equilibrium via a Primal-Dual-Type Algorithm. FOCS 2002 : 389-395 Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou: Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. ICALP 2002 : 110-122 Christos H. Papadimitriou: The Internet, the Web, and Algorithms. LATIN 2002 : 2 Joan Feigenbaum , Christos H. Papadimitriou, Rahul Sami , Scott Shenker : A BGP-based mechanism for lowest-cost routing. PODC 2002 : 173-182 Milena Mihail , Christos H. Papadimitriou: On the Eigenvalue Power Law. RANDOM 2002 : 254-262 Christos H. Papadimitriou: Understanding the Internet. SETN 2002 : 1-2 Aditya Akella , Srinivasan Seshan , Richard M. Karp , Scott Shenker , Christos H. Papadimitriou: Selfish behavior and stability of the internet: a game-theoretic analysis of TCP. SIGCOMM 2002 : 117-130 Christos H. Papadimitriou: The Joy of Theory. STOC 2002 : 116 Xiaotie Deng , Christos H. Papadimitriou, Shmuel Safra : On the complexity of equilibria. STOC 2002 : 67-71 Joseph M. Hellerstein , Elias Koutsoupias , Daniel P. Miranker , Christos H. Papadimitriou, Vasilis Samoladas : On a model of indexability and its bounds for range queries. J. ACM 49 (1): 35-55 (2002) Zhi-Zhong Chen , Michelangelo Grigni , Christos H. Papadimitriou: Map graphs. J. ACM 49 (2): 127-138 (2002) Yannis E. Ioannidis , Christos H. Papadimitriou: Special Issue on PODS 1999 - Guest Editors' Foreword. J. Comput. Syst. Sci. 64 (3): 441-442 (2002) Evgeny Dantsin , Andreas Goerdt , Edward A. Hirsch , Ravi Kannan , Jon M. Kleinberg , Christos H. Papadimitriou, Prabhakar Raghavan , Uwe Schöning : A deterministic (2-2/(k+1)) n algorithm for k-SAT based on local search. Theor. Comput. Sci. 289 (1): 69-83 (2002) Christos H. Papadimitriou: Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. FOCS 2001 : 4-8 Christos H. Papadimitriou: Algorithmic problems related to the Internet. HERCMA 2001 : 92 Christos H. Papadimitriou: Algorithms, Games, and the Internet. ICALP 2001 : 1-3 Christos H. Papadimitriou, Mihalis Yannakakis : Multiobjective Query Optimization. PODS 2001 Christos H. Papadimitriou: Game theory, algorithms, and the Internet. SODA 2001 : 391 Christos H. Papadimitriou: Algorithms, games, and the internet. STOC 2001 : 749-753 Pierluigi Crescenzi , Xiaotie Deng , Christos H. Papadimitriou: On Approximating a Scheduling Problem. J. Comb. Optim. 5 (3): 287-297 (2001) Joan Feigenbaum , Christos H. Papadimitriou, Scott Shenker : Sharing the Cost of Multicast Transmissions. J. Comput. Syst. Sci. 63 (1): 21-41 (2001) Vincent D. Blondel , Olivier Bournez , Pascal Koiran , Christos H. Papadimitriou, John N. Tsitsiklis : Deciding stability and mortality of piecewise affine dynamical systems. Theor. Comput. Sci. 255 (1-2): 687-696 (2001) Christos H. Papadimitriou: Theoretical Problems Related to the Internet. COCOON 2000 : 1-2 Richard M. Karp , Elias Koutsoupias , Christos H. Papadimitriou, Scott Shenker : Optimization Problems in Congestion Control. FOCS 2000 : 66-74 Christos H. Papadimitriou, Mihalis Yannakakis : On the Approximability of Trade-offs and Optimal Access of Web Sources. FOCS 2000 : 86-92 Christos H. Papadimitriou: On certain rigorous approaches to data mining (invited talk, abstract only). KDD 2000 : 2 Jon M. Kleinberg , Christos H. Papadimitriou, Prabhakar Raghavan : Auditing Boolean Attributes. PODS 2000 : 86-91 Christos H. Papadimitriou, Santosh Vempala : On the approximability of the traveling salesman problem (extended abstract). STOC 2000 : 126-133 Joan Feigenbaum , Christos H. Papadimitriou, Scott Shenker : Sharing the cost of muliticast transmissions (preliminary version). STOC 2000 : 218-227 Christos H. Papadimitriou, Prabhakar Raghavan , Hisao Tamaki , Santosh Vempala : Latent Semantic Indexing: A Probabilistic Analysis. J. Comput. Syst. Sci. 61 (2): 217-235 (2000) Richard Desper , Feng Jiang , Olli-P. Kallioniemi , Holger Moch , Christos H. Papadimitriou, Alejandro A. Schäffer : Distance-Based Reconstruction of Tree Models for Oncogenesis. Journal of Computational Biology 7 (6): 789-803 (2000) Elias Koutsoupias , Christos H. Papadimitriou: Beyond Competitive Analysis. SIAM J. Comput. 30 (1): 300-317 (2000) Michelangelo Grigni , Vincent Mirelli , Christos H. Papadimitriou: On the Difficulty of Designing Good Classifiers. SIAM J. Comput. 30 (1): 318-323 (2000) Kenneth A. Ross , Yannis E. Ioannidis , Anant Jhingran , Christos H. Papadimitriou: Reminiscences on Influential Papers. SIGMOD Record 29 (4): 48-49 (2000) Gene Cheung , Steven McCanne , Christos H. Papadimitriou: Software Synthesis of Variable-length Code Decoder Using a Mixture of Programmed Logic and Table Lookups. Data Compression Conference 1999 : 121-130 Deborah Goldman , Sorin Istrail , Christos H. Papadimitriou: Algorithmic Aspects of Protein Structure Similarity. FOCS 1999 : 512-522 Christos H. Papadimitriou: Novel Computational Approaches to Information Retrieval and Data Mining (Abstract). ICDT 1999 : 31 Georg Gottlob , Christos H. Papadimitriou: On the Complexity of Single-Rule Datalog Queries. LPAR 1999 : 201-222 Christos H. Papadimitriou: Topological Queries. SSD 1999 : 3-4 Elias Koutsoupias , Christos H. Papadimitriou: Worst-case Equilibria. STACS 1999 : 404-413 Christos H. Papadimitriou, Dan Suciu , Victor Vianu : Topological Queries in Spatial Databases. J. Comput. Syst. Sci. 58 (1): 29-53 (1999) Christos H. Papadimitriou, Mihalis Yannakakis : On the Complexity of Database Queries. J. Comput. Syst. Sci. 58 (3): 407-427 (1999) Christos H. Papadimitriou, Martha Sideri : On the Floyd-Warshall Algorithm for Logic Programs. J. Log. Program. 41 (1): 129-137 (1999) Richard Desper , Feng Jiang , Olli-P. Kallioniemi , Holger Moch , Christos H. Papadimitriou, Alejandro A. Schäffer : Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data. Journal of Computational Biology 6 (1): 37-52 (1999) Christos H. Papadimitriou: Algorithmic Approaches to Information Retrieval and Data Mining (Abstract). COCOON 1998 : 1 Christos H. Papadimitriou, Prabhakar Raghavan , Hisao Tamaki , Santosh Vempala : Latent Semantic Indexing: A Probabilistic Analysis. PODS 1998 : 159-168 Pierluigi Crescenzi , Deborah Goldman , Christos H. Papadimitriou, Antonio Piccolboni , Mihalis Yannakakis : On the complexity of protein folding (abstract). RECOMB 1998 : 61-62 Jon M. Kleinberg , Christos H. Papadimitriou, Prabhakar Raghavan : Segmentation Problems. STOC 1998 : 473-482 Zhi-Zhong Chen , Michelangelo Grigni , Christos H. Papadimitriou: Planar Map Graphs. STOC 1998 : 514-523 Pierluigi Crescenzi , Deborah Goldman , Christos H. Papadimitriou, Antonio Piccolboni , Mihalis Yannakakis : On the Complexity of Protein Folding (Extended Abstract). STOC 1998 : 597-603 Jon M. Kleinberg , Christos H. Papadimitriou, Prabhakar Raghavan : A Microeconomic View of Data Mining. Data Min. Knowl. Discov. 2 (4): 311-324 (1998) Serge Abiteboul , Christos H. Papadimitriou, Victor Vianu : Reflective Relational Machines. Inf. Comput. 143 (2): 110-136 (1998) Xiaotie Deng , Tiko Kameda , Christos H. Papadimitriou: How to Learn an Unknown Environment I: The Rectilinear Case. J. ACM 45 (2): 215-245 (1998) Goran Gogic , Christos H. Papadimitriou, Martha Sideri : Incremental Recompilation of Knowledge. JAIR 8 : 23-37 (1998) Pierluigi Crescenzi , Deborah Goldman , Christos H. Papadimitriou, Antonio Piccolboni , Mihalis Yannakakis : On the Complexity of Protein Folding. Journal of Computational Biology 5 (3): 423-466 (1998) Christos H. Papadimitriou: Planar Topological Queries. CDB 1997 : 1-6 Christos H. Papadimitriou: NP-Completeness: A Retrospective. ICALP 1997 : 2-6 Xiaotie Deng , Christos H. Papadimitriou: Decision-Making by Hierarchies of Discordant Agents. ISAAC 1997 : 183-192 Christos H. Papadimitriou, Mihalis Yannakakis : On the Complexity of Database Queries. PODS 1997 : 12-19 Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997 : 249-256 Zhi-Zhong Chen , Michelangelo Grigni , Christos H. Papadimitriou: Panarity, Revisited (Extended Abstract). WADS 1997 : 472-473 Yannis Dimopoulos , Vangelis Magirou , Christos H. Papadimitriou: On Kernels, Defaults and Even Graphs. Ann. Math. Artif. Intell. 20 (1-4): 1-12 (1997) Christos H. Papadimitriou, Mihalis Yannakakis : Tie-Breaking Semantics and Structural Totality. J. Comput. Syst. Sci. 54 (1): 48-60 (1997) Michelangelo Grigni , Vincent Mirelli , Christos H. Papadimitriou: On the Difficulty of Designing Good Classifiers. COCOON 1996 : 273-279 Christos H. Papadimitriou: Computational Aspacts of Organization Theory (Extended Abstract). ESA 1996 : 559-564 Elias Koutsoupias , Christos H. Papadimitriou, Mihalis Yannakakis : Searching a Fixed Graph. ICALP 1996 : 280-289 Christos H. Papadimitriou: The Complexity of Knowledge Representation. IEEE Conference on Computational Complexity 1996 : 244-248 Serge Abiteboul , Gabriel M. Kuper , Christos H. Papadimitriou, Moshe Y. Vardi : In Memoriam: Paris C. Kanellakis. PODS 1996 : 79 Christos H. Papadimitriou, Dan Suciu , Victor Vianu : Topological Queries in Spatial Databases. PODS 1996 : 81-92 Xiaotie Deng , Christos H. Papadimitriou: Competitive Distributed Decision-Making. Algorithmica 16 (2): 133-150 (1996) Elias Koutsoupias , Christos H. Papadimitriou: The 2-Evader Problem. Inf. Process. Lett. 57 (5): 249-252 (1996) Christos H. Papadimitriou, Mihalis Yannakakis : On Limited Nondeterminism and the Complexity of the V-C Dimension. J. Comput. Syst. Sci. 53 (2): 161-170 (1996) Christos H. Papadimitriou, Martha Sideri : The Bisection Width of Grid Graphs. Mathematical Systems Theory 29 (2): 97-110 (1996) Michelangelo Grigni , Elias Koutsoupias , Christos H. Papadimitriou: An Approximation Scheme for Planar Graph TSP. FOCS 1995 : 640-645 Goran Gogic , Henry A. Kautz , Christos H. Papadimitriou, Bart Selman : The Comparative Linguistics of Knowledge Representation. IJCAI (1) 1995 : 862-869 Michelangelo Grigni , Dimitris Papadias , Christos H. Papadimitriou: Topological Inference. IJCAI (1) 1995 : 901-907 Christos H. Papadimitriou, Srinivas Ramanathan , P. Venkat Rangan : Optimal Information Delivery. ISAAC 1995 : 181-187 Christos H. Papadimitriou: Database Metatheory: Asking the Big Queries. PODS 1995 : 1-10 Christos H. Papadimitriou, Srinivas Ramanathan , P. Venkat Rangan , Srihari Sampathkumar : Multimedia Information Caching for Personalized Video-on-Demand. Computer Communications 18 (3): 204-216 (1995) Elias Koutsoupias , Christos H. Papadimitriou: On the k-Server Conjecture. J. ACM 42 (5): 971-983 (1995) Pierluigi Crescenzi , Christos H. Papadimitriou: Reversible Simulation of Space-Bounded Computations. Theor. Comput. Sci. 143 (1): 159-165 (1995) Goran Gogic , Christos H. Papadimitriou, Martha Sideri : Incremental Recompilation of Knowledge. AAAI 1994 : 922-927 Milena Mihail , Christos H. Papadimitriou: On the Random Walk Method for Protocol Testing. CAV 1994 : 132-141 Elias Koutsoupias , Christos H. Papadimitriou: Beyond Competitive Analysis FOCS 1994 : 394-400 Christos H. Papadimitriou, Prabhakar Raghavan , Madhu Sudan , Hisao Tamaki : Motion Planning on a Graph (Extended Abstract) FOCS 1994 : 511-520 Christos H. Papadimitriou, Srinivas Ramanathan , P. Venkat Rangan : Information Caching for Delivery of Personalized Video Programs on Home Entertainment Channels. ICMCS 1994 : 214-223 Serge Abiteboul , Christos H. Papadimitriou, Victor Vianu : The Power of Reflective Relational Machines LICS 1994 : 230-240 Christos H. Papadimitriou, Mihalis Yannakakis : On complexity as bounded rationality (extended abstract). STOC 1994 : 726-733 Christos H. Papadimitriou, John N. Tsitsiklis : The Complexity of Optimal Queueing Network Control. Structure in Complexity Theory Conference 1994 : 318-322 Christos H. Papadimitriou, P. Venkat Rangan , Martha Sideri : Designing Secure Communication Protocols from Trust Specification. Algorithmica 11 (5): 485-499 (1994) Christos H. Papadimitriou, Martha Sideri : Default Theories that Always Have Extensions. Artif. Intell. 69 (1-2): 347-357 (1994) Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48 (3): 498-532 (1994) Elias Dahlhaus , David S. Johnson , Christos H. Papadimitriou, Paul D. Seymour , Mihalis Yannakakis : The Complexity of Multiterminal Cuts. SIAM J. Comput. 23 (4): 864-894 (1994) Dimitris J. Kavvadias , Christos H. Papadimitriou, Martha Sideri : On Horn Envelopes and Hypergraph Transversals. ISAAC 1993 : 399-405 Christos H. Papadimitriou, Mihalis Yannakakis : Linear programming without the matrix. STOC 1993 : 121-129 Christos H. Papadimitriou, Mihalis Yannakakis : On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract). Structure in Complexity Theory Conference 1993 : 12-18 Christos H. Papadimitriou, Paolo Serafini , Mihalis Yannakakis : Computing the Throughput of a Network with Dedicated Lines. Discrete Applied Mathematics 42 (2): 271-278 (1993) Foto N. Afrati , Christos H. Papadimitriou: The Parallel Complexity of Simple Logic Programs. J. ACM 40 (4): 891-916 (1993) Christos H. Papadimitriou, Martha Sideri : On Finding Extensions of Default Theories. ICDT 1992 : 276-281 Xiaotie Deng , Christos H. Papadimitriou: Competitive Distributed Decision-Making. IFIP Congress (1) 1992 : 350-356 Christos H. Papadimitriou, Mihalis Yannakakis : Tie-Breaking Semantics and Structural Totality. PODS 1992 : 16-22 Elias Dahlhaus , David S. Johnson , Christos H. Papadimitriou, Paul D. Seymour , Mihalis Yannakakis : The Complexity of Multiway Cuts (Extended Abstract) STOC 1992 : 241-251 Elias Koutsoupias , Christos H. Papadimitriou: On the Greedy Algorithm for Satisfiability. Inf. Process. Lett. 43 (1): 53-55 (1992) Christos H. Papadimitriou: The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem. SIAM J. Comput. 21 (3): 450-465 (1992) Christos H. Papadimitriou: On Selecting a Satisfying Truth Assignment (Extended Abstract) FOCS 1991 : 163-169 Xiaotie Deng , Tiko Kameda , Christos H. Papadimitriou: How to Learn an Unknown Environment (Extended Abstract) FOCS 1991 : 298-303 Christos H. Papadimitriou, P. Venkat Rangan , Martha Sideri : Designing Secure Communication Protocols from Trust Specifications. FSTTCS 1991 : 360-368 Christos H. Papadimitriou: Decision-Making with Incomplete Information. ISA 1991 : 1 Christos H. Papadimitriou, Mihalis Yannakakis : On the Value of Information in Distributed Decision-Making (Extended Abstract). PODC 1991 : 61-64 Christos H. Papadimitriou, Martha Sideri : Optimal Coteries. PODC 1991 : 75-80 Joseph S. B. Mitchell , Christos H. Papadimitriou: The Weighted Region Problem: Finding Shortest Paths Through a Weighted Planar Subdivision. J. ACM 38 (1): 18-73 (1991) Esther M. Arkin , Christos H. Papadimitriou, Mihalis Yannakakis : Modularity of Cycles and Paths in Graphs. J. ACM 38 (2): 255-274 (1991) Phokion G. Kolaitis , Christos H. Papadimitriou: Why not Negation by Fixpoint? J. Comput. Syst. Sci. 43 (1): 125-144 (1991) Christos H. Papadimitriou, Mihalis Yannakakis : Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci. 43 (3): 425-440 (1991) Nimrod Megiddo , Christos H. Papadimitriou: On Total Functions, Existence Theorems and Computational Complexity. Theor. Comput. Sci. 81 (2): 317-324 (1991) Christos H. Papadimitriou, Mihalis Yannakakis : Shortest Paths Without a Map. Theor. Comput. Sci. 84 (1): 127-150 (1991) Xiaotie Deng , Christos H. Papadimitriou: Exploring an Unknown Graph (Extended Abstract) FOCS 1990 : 355-361 Samuel R. Buss , Christos H. Papadimitriou, John N. Tsitsiklis : On the Predictability of Coupled Automata: An Allegory about Chaos FOCS 1990 : 788-793 Christos H. Papadimitriou: On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract) FOCS 1990 : 794-801 Christos H. Papadimitriou, Martha Sideri : The Bisection Width of Grid Graphs. SODA 1990 : 405-410 Christos H. Papadimitriou, Alejandro A. Schäffer , Mihalis Yannakakis : On the Complexity of Local Search (Extended Abstract) STOC 1990 : 438-445 Elias Koutsoupias , Christos H. Papadimitriou, Martha Sideri : On the Optimal Bisection of a Polygon (Extended Abstract). Symposium on Computational Geometry 1990 : 198-202 Dimitris J. Kavvadias , Christos H. Papadimitriou: A Linear Programming Approach to Reasoning about Probabilities. Ann. Math. Artif. Intell. 1 : (1990) Christos H. Papadimitriou, Mihalis Yannakakis : On recognizing integer polyhedra. Combinatorica 10 (1): 107-109 (1990) Xanthippi Markenscoff , Luqun Ni , Christos H. Papadimitriou: The Geometry of Grasping. I. J. Robotic Res. 9 (1): 61-74 (1990) John G. Kollias , Yannis Manolopoulos , Christos H. Papadimitriou: The Optimum Execution Order of Queries in Linear Storage. Inf. Process. Lett. 36 (3): 141-145 (1990) Phokion G. Kolaitis , Christos H. Papadimitriou: Some Computational Aspects of Circumscription J. ACM 37 (1): 1-14 (1990) Christos H. Papadimitriou, Mihalis Yannakakis : Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput. 19 (2): 322-328 (1990) Christos H. Papadimitriou, Mihalis Yannakakis : Shortest Paths Without a Map. ICALP 1989 : 610-620 Xanthippi Markenscoff , Christos H. Papadimitriou: Optimum Grip of a Polygon. I. J. Robotic Res. 8 (2): 17-29 (1989) Foto N. Afrati , Christos H. Papadimitriou, George Papageorgiou : Corrigendum: The Complexity of Cubical Graphs Inf. Comput. 82 (3): 350-353 (1989) Ellen B. Feinberg , Christos H. Papadimitriou: Finding Feasible Paths for a Two-Point Body. J. Algorithms 10 (1): 109-119 (1989) Foto N. Afrati , Christos H. Papadimitriou, George Papageorgiou , Athena Roussou , Yehoshua Sagiv , Jeffrey D. Ullman : On the Convergence of Query Evaluation. J. Comput. Syst. Sci. 38 (2): 341-359 (1989) Phokion G. Kolaitis , Christos H. Papadimitriou: Some Computational Aspects of Circumscription. AAAI 1988 : 455-469 Foto N. Afrati , Christos H. Papadimitriou, George Papageorgiou : Scheduling Dags to Minimize Time and Communication. AWOC 1988 : 134-138 Phokion G. Kolaitis , Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988 : 231-239 Christos H. Papadimitriou, Mihalis Yannakakis : Optimization, Approximation, and Complexity Classes (Extended Abstract) STOC 1988 : 229-234 Christos H. Papadimitriou, Mihalis Yannakakis : Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract) STOC 1988 : 510-513 Foto N. Afrati , Christos H. Papadimitriou, George Papageorgiou : The Synthesis of Communication Protocols. Algorithmica 3 : 451-472 (1988) Sophocles Ephremidis , Christos H. Papadimitriou, Martha Sideri : Complexity Characterizations of Attribute Grammar Languages Inf. Comput. 78 (3): 178-186 (1988) David S. Johnson , Christos H. Papadimitriou: On Generating All Maximal Independent Sets. Inf. Process. Lett. 27 (3): 119-123 (1988) Nimrod Megiddo , S. Louis Hakimi , M. R. Garey , David S. Johnson , Christos H. Papadimitriou: The complexity of searching a graph. J. ACM 35 (1): 18-44 (1988) Lefteris M. Kirousis , Christos H. Papadimitriou: The Complexity of Recognizing Polyhedral Scenes. J. Comput. Syst. Sci. 37 (1): 14-38 (1988) Christos H. Papadimitriou, David Wolfe : The Complexity of Facets Resolved. J. Comput. Syst. Sci. 37 (1): 2-13 (1988) David S. Johnson , Christos H. Papadimitriou, Mihalis Yannakakis : How Easy is Local Search? J. Comput. Syst. Sci. 37 (1): 79-100 (1988) Foto N. Afrati , Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987 : 210-213 Joseph S. B. Mitchell , Christos H. Papadimitriou: The Weighted Region Problem. Symposium on Computational Geometry 1987 : 30-38 Christos H. Papadimitriou, Ellen B. Silverberg : Optimal Piecewise Linear Motion of an Object Among Obstacles. Algorithmica 2 : 523-539 (1987) George Georgakopoulos , Christos H. Papadimitriou: The 1-Steiner Tree Problem. J. Algorithms 8 (1): 122-130 (1987) Christos H. Papadimitriou, John N. Tsitsiklis : On Stochastic Scheduling with In-Tree Precedence Constraints. SIAM J. Comput. 16 (1): 1-6 (1987) Christos H. Papadimitriou, Mihalis Yannakakis : The Complexity of Reliable Concurrency Control. SIAM J. Comput. 16 (3): 538-553 (1987) Christos H. Papadimitriou, Jeffrey D. Ullman : A Communication-Time Tradeoff. SIAM J. Comput. 16 (4): 639-646 (1987) Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou: The Discrete Geodesic Problem. SIAM J. Comput. 16 (4): 647-668 (1987) Christos H. Papadimitriou: The Theory of Database Concurrency Control Computer Science Press 1986 Christos H. Papadimitriou: Shortest-Path Motion. FSTTCS 1986 : 144-153 Foto N. Afrati , Christos H. Papadimitriou, Georgios I. Papadimitriou : The Synthesis of Communication Protocols. PODC 1986 : 263-271 Foto N. Afrati , Christos H. Papadimitriou, George Papageorgiou , Athena Roussou , Yehoshua Sagiv , Jeffrey D. Ullman : Convergence of Sideways Query Evaluation. PODS 1986 : 24-30 Foto N. Afrati , Stavros S. Cosmadakis , Christos H. Papadimitriou, George Papageorgiou , Nadia Papakostantinou : The Complexity of the Travelling Repairman Problem. ITA 20 (1): 79-87 (1986) Christos H. Papadimitriou, Mihalis Yannakakis : A Note on Succinct Representations of Graphs Information and Control 71 (3): 181-185 (1986) John N. Tsitsiklis , Christos H. Papadimitriou, Pierre A. Humblet : The performance of a precedence-based queuing discipline. J. ACM 33 (3): 593-602 (1986) Esther M. Arkin , Christos H. Papadimitriou: On the Complexity of Circulations. J. Algorithms 7 (1): 134-145 (1986) Thanasis Hadzilacos , Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. J. Comput. Syst. Sci. 33 (2): 297-310 (1986) Lefteris M. Kirousis , Christos H. Papadimitriou: Searching and Pebbling. Theor. Comput. Sci. 47 (3): 205-218 (1986) Lefteris M. Kirousis , Christos H. Papadimitriou: The Complexity of Recognizing Polyhedral Scenes (Extended Abstract) FOCS 1985 : 175-185 David S. Johnson , Christos H. Papadimitriou, Mihalis Yannakakis : How Easy Is Local Search? (Extended Abstract) FOCS 1985 : 39-42 Christos H. Papadimitriou, David Wolfe : The Complexity of Facets Resolved FOCS 1985 : 74-78 Christos H. Papadimitriou, Mihalis Yannakakis : The Complexity of Reliable Concurrency Control. PODS 1985 : 230-234 Thanasis Hadzilacos , Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. PODS 1985 : 96-104 Christos H. Papadimitriou: A note the expressive power of Prolog. Bulletin of the EATCS 26 : 21-22 (1985) Christos H. Papadimitriou: An Algorithm for Shortest-Path Motion in Three Dimensions. Inf. Process. Lett. 20 (5): 259-263 (1985) Foto N. Afrati , Christos H. Papadimitriou, George Papageorgiou : The Complexity of Cubical Graphs Information and Control 66 (1/2): 53-60 (1985) Christos H. Papadimitriou: Correction to ``A Theorem in Database Concurrency Control'' J. ACM 32 (3): 750 (1985) Christos H. Papadimitriou: Games Against Nature. J. Comput. Syst. Sci. 31 (2): 288-301 (1985) Paris C. Kanellakis , Christos H. Papadimitriou: The Complexity of Distributed Concurrency Control. SIAM J. Comput. 14 (1): 52-74 (1985) Christos H. Papadimitriou, Jeffrey D. Ullman : A Communication-Time Tradeoff FOCS 1984 : 84-88 Foto N. Afrati , Christos H. Papadimitriou, George Papageorgiou : The Complexity of Cubical Graphs (Extended Abstract). ICALP 1984 : 51-57 Christos H. Papadimitriou, Paris C. Kanellakis : On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9 (1): 89-99 (1984) Christos H. Papadimitriou: On the complexity of unique solutions. J. ACM 31 (2): 392-400 (1984) Stavros S. Cosmadakis , Christos H. Papadimitriou: Updates of Relational Views. J. ACM 31 (4): 742-760 (1984) Christos H. Papadimitriou, Umesh V. Vazirani : On Two Geometric Problems Related to the Traveling Salesman Problem. J. Algorithms 5 (2): 231-246 (1984) Paris C. Kanellakis , Christos H. Papadimitriou: Is Distributed Locking Harder? J. Comput. Syst. Sci. 28 (1): 103-120 (1984) Marco A. Casanova , Ronald Fagin , Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. J. Comput. Syst. Sci. 28 (1): 29-59 (1984) Christos H. Papadimitriou, Mihalis Yannakakis : The Complexity of Facets (and Some Facets of Complexity). J. Comput. Syst. Sci. 28 (2): 244-259 (1984) Christos H. Papadimitriou, Michael Sipser : Communication Complexity. J. Comput. Syst. Sci. 28 (2): 260-269 (1984) Stavros S. Cosmadakis , Christos H. Papadimitriou: The Traveling Salesman Problem with Many Visits to Few Cities. SIAM J. Comput. 13 (1): 99-108 (1984) Fillia Makedon , Christos H. Papadimitriou, Ivan Hal Sudborough : Topological Bandwidth. CAAP 1983 : 317-331 Christos H. Papadimitriou: Games Against Nature (Extended Abstract) FOCS 1983 : 446-450 Mihalis Yannakakis , Paris C. Kanellakis , Stavros S. Cosmadakis , Christos H. Papadimitriou: Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract). ICALP 1983 : 712-722 Stavros S. Cosmadakis , Christos H. Papadimitriou: Updates of Relational Views. PODS 1983 : 317-331 Christos H. Papadimitriou, Stathis Zachos : Two remarks on the power of counting. Theoretical Computer Science 1983 : 269-276 Christos H. Papadimitriou: Theory of concurrency control. Theoretical Computer Science 1983 : 35-47 H. T. Kung , Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. Acta Inf. 19 : 1-11 (1983) Christos H. Papadimitriou: Concurrency Control by Locking. SIAM J. Comput. 12 (2): 215-226 (1983) Christos H. Papadimitriou, Kenneth Steiglitz : Combinatorial Optimization: Algorithms and Complexity Prentice-Hall 1982 Christos H. Papadimitriou: On the Complexity of Unique Solutions FOCS 1982 : 14-20 Marco A. Casanova , Ronald Fagin , Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982 : 171-176 Christos H. Papadimitriou, Paris C. Kanellakis : On Concurrency Control by Multiple Versions. PODS 1982 : 76-82 Paris C. Kanellakis , Christos H. Papadimitriou: Is Distributed Locking Harder? PODS 1982 : 98-107 Christos H. Papadimitriou, Michael Sipser : Communication Complexity STOC 1982 : 196-200 Christos H. Papadimitriou, Mihalis Yannakakis : The Complexity of Facets (and Some Facets of Complexity) STOC 1982 : 255-260 Christos H. Papadimitriou, John N. Tsitsiklis : On the Complexity of Designing Distributed Protocols Information and Control 53 (3): 211-218 (1982) Christos H. Papadimitriou, Mihalis Yannakakis : The complexity of restricted spanning tree problems. J. ACM 29 (2): 285-309 (1982) Christos H. Papadimitriou: A theorem in database concurrency control. J. ACM 29 (4): 998-1006 (1982) Mihalis Yannakakis , Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25 (1): 2-41 (1982) Richard M. Karp , Christos H. Papadimitriou: On Linear Characterizations of Combinatorial Optimization Problems. SIAM J. Comput. 11 (4): 620-632 (1982) Alon Itai , Christos H. Papadimitriou, Jayme Luiz Szwarcfiter : Hamilton Paths in Grid Graphs. SIAM J. Comput. 11 (4): 676-686 (1982) Harry R. Lewis , Christos H. Papadimitriou: Symmetric Space-Bounded Computation. Theor. Comput. Sci. 19 : 161-187 (1982) Harry R. Lewis , Christos H. Papadimitriou: Elements of the Theory of Computation Prentice-Hall 1981 Paris C. Kanellakis , Christos H. Papadimitriou: The Complexity of Distributed Concurrency Control FOCS 1981 : 185-197 Christos H. Papadimitriou, Mihalis Yannakakis : Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract) FOCS 1981 : 358-363 Nimrod Megiddo , S. Louis Hakimi , M. R. Garey , David S. Johnson , Christos H. Papadimitriou: The Complexity of Searching a Graph (Preliminary Version) FOCS 1981 : 376-385 Christos H. Papadimitriou: On the Power of Locking. SIGMOD Conference 1981 : 148-154 Christos H. Papadimitriou, Mihalis Yannakakis : On Minimal Eulerian Graphs. Inf. Process. Lett. 12 (4): 203-205 (1981) Christos H. Papadimitriou, Mihalis Yannakakis : The Clique Problem for Planar Graphs. Inf. Process. Lett. 13 (4/5): 131-133 (1981) Manuel Blum , Richard M. Karp , Oliver Vornberger , Christos H. Papadimitriou, Mihalis Yannakakis : The Complexity of Testing Whether a Graph is a Superconcentrator. Inf. Process. Lett. 13 (4/5): 164-167 (1981) Christos H. Papadimitriou: On the complexity of integer programming. J. ACM 28 (4): 765-768 (1981) Witold Lipski Jr. , Christos H. Papadimitriou: A Fast Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems. J. Algorithms 2 (3): 211-226 (1981) Christos H. Papadimitriou: Worst-Case and Probabilistic Analysis of a Geometric Location Problem. SIAM J. Comput. 10 (3): 542-557 (1981) Alon Itai , Richard J. Lipton , Christos H. Papadimitriou, Michael Rodeh : Covering Graphs by Simple Circuits. SIAM J. Comput. 10 (4): 746-750 (1981) Richard M. Karp , Christos H. Papadimitriou: On Linear Characterizations of Combinatorial Optimization Problems FOCS 1980 : 1-9 Mihalis Yannakakis , Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract) FOCS 1980 : 328-332 Harry R. Lewis , Christos H. Papadimitriou: Symmetric Space-Bounded Computation (Extended Abstract). ICALP 1980 : 374-384 Christos H. Papadimitriou, Jon Louis Bentley : A Worst-Case Analysis of Nearest Neighbor Searching by Projection. ICALP 1980 : 470-482 Christos H. Papadimitriou, Philip A. Bernstein : On the Performance of Balanced Hashing Functions When the Keys Are Not Equiprobable. ACM Trans. Program. Lang. Syst. 2 (1): 77-89 (1980) Christos H. Papadimitriou, Paris C. Kanellakis : Flowshop scheduling with limited temporary storage. J. ACM 27 (3): 533-549 (1980) Mihalis Yannakakis , Christos H. Papadimitriou, H. T. Kung : Locking Policies: Safety and Freedom from Deadlock FOCS 1979 : 286-297 Christos H. Papadimitriou, Mihalis Yannakakis : The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). ICALP 1979 : 460-470 H. T. Kung , Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979 : 116-126 Christos H. Papadimitriou: Efficient Search for Rationals. Inf. Process. Lett. 8 (1): 1-4 (1979) Christos H. Papadimitriou: Optimality of the Fast Fourier transform. J. ACM 26 (1): 95-102 (1979) Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26 (4): 631-653 (1979) Christos H. Papadimitriou, Mihalis Yannakakis : Scheduling Interval-Ordered Tasks. SIAM J. Comput. 8 (3): 405-409 (1979) Philip A. Bernstein , James B. Rothnie Jr. , Nathan Goodman , Christos H. Papadimitriou: The Concurrency Control Mechanism of SDD-1: A System for Distributed Databases (The Fully Redundant Case). IEEE Trans. Software Eng. 4 (3): 154-168 (1978) Christos H. Papadimitriou, Kenneth Steiglitz : On the Complexity of Local Search for the Traveling Salesman Problem. SIAM J. Comput. 6 (1): 76-83 (1977) Christos H. Papadimitriou: The Euclidean Traveling Salesman Problem is NP-Complete. Theor. Comput. Sci. 4 (3): 237-244 (1977) Christos H. Papadimitriou, Kenneth Steiglitz : Some Complexity Results for the Traveling Salesman Problem STOC 1976 : 1-9 Christos H. Papadimitriou: On the complexity of edge traversing. J. ACM 23 (3): 544-554 (1976) 1 [ 151 ] [ 170 ] [ 186 ] 2 [ 62 ] [ 67 ] [ 80 ] [ 81 ] [ 82 ] [ 92 ] [ 99 ] [ 103 ] [ 105 ] [ 107 ] [ 140 ] 3 [ 231 ] 4 [ 243 ] 5 [ 77 ] [ 126 ] 6 [ 15 ] 7 [ 5 ] [ 14 ] 8 [ 216 ] 9 [ 23 ] 10 [ 216 ] 11 [ 120 ] 12 [ 42 ] [ 56 ] 13 [ 177 ] [ 189 ] [ 227 ] 14 [ 203 ] 15 [ 49 ] [ 50 ] [ 53 ] [ 59 ] [ 80 ] 16 [ 157 ] [ 183 ] [ 188 ] [ 191 ] [ 218 ] 17 [ 136 ] [ 145 ] 18 [ 225 ] 19 [ 121 ] [ 132 ] [ 138 ] [ 168 ] [ 180 ] [ 185 ] [ 218 ] [ 229 ] [ 239 ] 20 [ 194 ] [ 207 ] 21 [ 237 ] 22 [ 176 ] 23 [ 249 ] 24 [ 98 ] 25 [ 236 ] [ 244 ] 26 [ 42 ] [ 56 ] 27 [ 209 ] [ 217 ] [ 234 ] 28 [ 106 ] 29 [ 27 ] [ 96 ] 30 [ 89 ] 31 [ 225 ] 32 [ 156 ] [ 163 ] [ 184 ] 33 [ 183 ] [ 188 ] [ 191 ] [ 202 ] 34 [ 5 ] 35 [ 200 ] [ 241 ] 36 [ 162 ] [ 164 ] [ 174 ] [ 177 ] [ 189 ] [ 205 ] [ 227 ] 37 [ 70 ] [ 76 ] 38 [ 27 ] [ 96 ] 39 [ 178 ] [ 228 ] 40 [ 225 ] 41 [ 78 ] 42 [ 204 ] [ 226 ] 43 [ 202 ] 44 [ 19 ] [ 32 ] 45 [ 204 ] 46 [ 194 ] [ 207 ] 47 [ 27 ] [ 73 ] [ 93 ] [ 96 ] [ 97 ] [ 136 ] [ 145 ] 48 [ 194 ] [ 207 ] 49 [ 132 ] [ 185 ] 50 [ 13 ] [ 29 ] [ 40 ] [ 41 ] [ 50 ] [ 57 ] [ 61 ] [ 64 ] 51 [ 225 ] 52 [ 18 ] [ 23 ] [ 33 ] [ 214 ] [ 231 ] [ 242 ] [ 249 ] 53 [ 163 ] 54 [ 115 ] [ 144 ] 55 [ 74 ] [ 75 ] [ 95 ] 56 [ 187 ] [ 190 ] [ 211 ] [ 225 ] [ 240 ] [ 248 ] 57 [ 216 ] 58 [ 102 ] [ 104 ] [ 111 ] [ 125 ] 59 [ 112 ] 60 [ 116 ] [ 135 ] [ 154 ] [ 158 ] [ 164 ] [ 167 ] [ 172 ] [ 178 ] [ 198 ] [ 206 ] [ 214 ] [ 228 ] [ 236 ] 61 [ 10 ] [ 12 ] [ 46 ] 62 [ 170 ] 63 [ 16 ] [ 30 ] [ 31 ] 64 [ 21 ] 65 [ 19 ] 66 [ 244 ] 67 [ 176 ] 68 [ 52 ] 69 [ 244 ] 70 [ 112 ] 71 [ 108 ] [ 113 ] 72 [ 203 ] 73 [ 27 ] [ 96 ] [ 123 ] 74 [ 155 ] [ 233 ] [ 246 ] 75 [ 228 ] 76 [ 174 ] [ 205 ] 77 [ 85 ] [ 91 ] [ 127 ] 78 [ 194 ] [ 207 ] 79 [ 85 ] 80 [ 113 ] 81 [ 162 ] 82 [ 82 ] 83 [ 62 ] [ 67 ] [ 80 ] [ 81 ] [ 99 ] [ 103 ] [ 105 ] [ 107 ] 84 [ 80 ] 85 [ 183 ] [ 188 ] [ 191 ] 86 [ 153 ] [ 187 ] [ 190 ] [ 192 ] [ 208 ] [ 211 ] [ 225 ] [ 240 ] [ 248 ] 87 [ 152 ] [ 159 ] [ 161 ] 88 [ 131 ] [ 148 ] [ 152 ] [ 159 ] [ 161 ] 89 [ 245 ] 90 [ 19 ] 91 [ 204 ] 92 [ 5 ] 93 [ 81 ] [ 105 ] 94 [ 237 ] [ 246 ] 95 [ 229 ] [ 239 ] 96 [ 81 ] [ 105 ] 97 [ 234 ] 98 [ 228 ] 99 [ 159 ] 100 [ 117 ] [ 194 ] [ 207 ] 101 [ 225 ] 102 [ 163 ] 103 [ 141 ] 104 [ 231 ] 105 [ 136 ] [ 145 ] 106 [ 209 ] [ 214 ] [ 217 ] [ 231 ] [ 234 ] [ 242 ] [ 244 ] [ 245 ] [ 249 ] 107 [ 98 ] [ 116 ] [ 118 ] [ 128 ] [ 131 ] [ 139 ] [ 144 ] [ 147 ] [ 148 ] [ 156 ] [ 165 ] [ 184 ] [ 195 ] 108 [ 90 ] 109 [ 39 ] [ 54 ] 110 [ 2 ] [ 4 ] [ 44 ] 111 [ 245 ] 112 [ 169 ] [ 197 ] 113 [ 153 ] 114 [ 52 ] 115 [ 32 ] 116 [ 243 ] 117 [ 153 ] [ 192 ] [ 208 ] 118 [ 243 ] 119 [ 37 ] [ 78 ] [ 88 ] [ 120 ] [ 149 ] [ 216 ] 120 [ 63 ] [ 81 ] [ 86 ] [ 105 ] 121 [ 170 ] 122 [ 58 ] 123 [ 237 ] 124 [ 192 ] [ 208 ] [ 210 ] 125 [ 151 ] [ 169 ] [ 186 ] [ 197 ] 126 [ 23 ] 127 [ 72 ] [ 94 ] 128 [ 6 ] [ 11 ] [ 12 ] [ 17 ] [ 23 ] [ 24 ] [ 25 ] [ 28 ] [ 34 ] [ 36 ] [ 38 ] [ 50 ] [ 55 ] [ 71 ] [ 73 ] [ 79 ] [ 87 ] [ 93 ] [ 100 ] [ 101 ] [ 109 ] [ 110 ] [ 114 ] [ 117 ] [ 122 ] [ 124 ] [ 126 ] [ 129 ] [ 136 ] [ 137 ] [ 141 ] [ 142 ] [ 143 ] [ 145 ] [ 150 ] [ 166 ] [ 172 ] [ 175 ] [ 179 ] [ 183 ] [ 188 ] [ 191 ] [ 196 ] [ 213 ] [ 221 ] 129 [ 48 ]  ©2004 Association for Computing Machinery |
