Christos H. Papadimitriou Online DBLP entries are available for Christos H. Papadimitriou and the following references. (The DiSC DBLP references below have been taken from the Novemember 1998 DBLP.) Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala: Latent Semantic Indexing: A Probabilistic Analysis. PODS 1998: 159-168 Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou: How to Learn an Unknown Environment I: The Rectilinear Case. JACM 45(2): 215-245 (1998) Christos H. Papadimitriou: Planar Topological Queries. CDB 1997: 1-6 Christos H. Papadimitriou: NP-Completeness: A Retrospective. ICALP 1997: 2-6 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 Christos H. Papadimitriou, Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. JCSS 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 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. IPL 57(5): 249-252 (1996) Christos H. Papadimitriou, Mihalis Yannakakis: On Limited Nondeterminism and the Complexity of the V-C Dimension. JCSS 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 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. JACM 42(5): 971-983 (1995) Pierluigi Crescenzi, Christos H. Papadimitriou: Reversible Simulation of Space-Bounded Computations. TCS 143(1): 159-165 (1995) Goran Gogic, Christos H. Papadimitriou, Martha Sideri: Incremental Recompilation of Knowledge. AAAI, Vol. 2 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 Elias Koutsoupias, Christos H. Papadimitriou: On the k-Server Conjecture. STOC 1994: 507-511 Christos H. Papadimitriou, Mihalis Yannakakis: On Complexity as Bounded Rationality (Extended Abstract). STOC 1994: 726-733 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. Artificial Intelligence 69(1-2): 347-357 (1994) Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. JCSS 48(3): 498-532 (1994) Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, P. D. Seymour, Mihalis Yannakakis: The Complexity of Multiterminal Cuts. SIAM J. Comput. 23(4): 864-894 (1994) Christos H. Papadimitriou, Mihalis Yannakakis: Linear Programming without the Matrix (Extended Abstract). STOC 1993: 121-129 Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Logic Programs. JACM 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, Vol. 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, P. 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. IPL 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, 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. JACM 38(1): 18-73 (1991) Esther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis: Modularity of Cycles and Paths in Graphs. JACM 38(2): 255-274 (1991) Phokion G. Kolaitis, Christos H. Papadimitriou: Why not Negation by Fixpoint? JCSS 43(1): 125-144 (1991) Christos H. Papadimitriou, Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes. JCSS 43(3): 425-440 (1991) Nimrod Megiddo, Christos H. Papadimitriou: On Total Functions, Existence Theorems and Computational Complexity. TCS 81(2): 317-324 (1991) Christos H. Papadimitriou, Mihalis Yannakakis: Shortest Paths Without a Map. TCS 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 John G. Kollias, Yannis Manolopoulos, Christos H. Papadimitriou: The Optimum Execution Order of Queries in Linear Storage. IPL 36(3): 141-145 (1990) Phokion G. Kolaitis, Christos H. Papadimitriou: Some Computational Aspects of Circumscription. JACM 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 Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou: Corrigendum: The Complexity of Cubical Graphs. Information and Computation 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. JCSS 38(2): 341-359 (1989) Phokion G. Kolaitis, Christos H. Papadimitriou: Some Computational Aspects of Circumscription. AAAI 1988: 455-469 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) David S. Johnson, Christos H. Papadimitriou: On Generating All Maximal Independent Sets. IPL 27(3): 119-123 (1988) Sophocles Ephremidis, Christos H. Papadimitriou, Martha Sideri: Complexity Characterizations of Attribute Grammar Languages. Information and Computation 78(3): 178-186 (1988) Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou: The Complexity of Searching a Graph. JACM 35(1): 18-44 (1988) Lefteris M. Kirousis, Christos H. Papadimitriou: The Complexity of Recognizing Polyhedral Scenes. JCSS 37(1): 14-38 (1988) Christos H. Papadimitriou, David Wolfe: The Complexity of Facets Resolved. JCSS 37(1): 2-13 (1988) David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy is Local Search? JCSS 37(1): 79-100 (1988) Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213 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) Foto N. Afrati, Christos H. Papadimitriou, George 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 Christos H. Papadimitriou, Mihalis Yannakakis: A Note on Succinct Representations of Graphs. Information and Control 71(3): 181-185 (1986) Esther M. Arkin, Christos H. Papadimitriou: On the Complexity of Circulations. J. Algorithms 7(1): 134-145 (1986) John N. Tsitsiklis, Christos H. Papadimitriou, Pierre Humblet: The Performance of a Precedence-Based Queuing Discipline. JACM 33(3): 593-602 (1986) Thanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. JCSS 33(2): 297-310 (1986) Lefteris M. Kirousis, Christos H. Papadimitriou: Searching and Pebbling. TCS 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: An Algorithm for Shortest-Path Motion in Three Dimensions. Information Processing Letters 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''. JACM 32(3): 750 (1985) Christos H. Papadimitriou: Games Against Nature. JCSS 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, Umesh V. Vazirani: On Two Geometric Problems Related to the Traveling Salesman Problem. J. Algorithms 5(2): 231-246 (1984) Christos H. Papadimitriou: On the Complexity of Unique Solutions. JACM 31(2): 392-400 (1984) Stavros S. Cosmadakis, Christos H. Papadimitriou: Updates of Relational Views. JACM 31(4): 742-760 (1984) Paris C. Kanellakis, Christos H. Papadimitriou: Is Distributed Locking Harder? JCSS 28(1): 103-120 (1984) Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. JCSS 28(1): 29-59 (1984) Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). JCSS 28(2): 244-259 (1984) Christos H. Papadimitriou, Michael Sipser: Communication Complexity. JCSS 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) Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. TODS 9(1): 89-99 (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 H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. Acta Informatica 19: 1-11 (1983) Christos H. Papadimitriou: Concurrency Control by Locking. SIAM J. Comput. 12(2): 215-226 (1983) 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. JACM 29(2): 285-309 (1982) Christos H. Papadimitriou: A Theorem in Database Concurrency Control. JACM 29(4): 998-1006 (1982) Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. JCSS 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. TCS 19: 161-187 (1982) 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. Information Processing Letters 12(4): 203-205 (1981) Christos H. Papadimitriou, Mihalis Yannakakis: The Clique Problem for Planar Graphs. Information Processing Letters 13(3): 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. Information Processing Letters 13(3): 164-167 (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: On the Complexity of Integer Programming. JACM 28(4): 765-768 (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, Paris C. Kanellakis: Flowshop Scheduling with Limited Temporary Storage. JACM 27(3): 533-549 (1980) Christos H. Papadimitriou, Philip A. Bernstein: On the Performance of Balanced Hashing Functions When the Keys Are Not Equiprobable. TOPLAS 2(1): 77-89 (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. Information Processing Letters 8(1): 1-4 (1979) Christos H. Papadimitriou: Optimality of the Fast Fourier Transform. JACM 26(1): 95-102 (1979) Christos H. Papadimitriou: The Serializability of Concurrent Database Updates. JACM 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). TSE 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. TCS 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. JACM 23(3): 544-554 (1976) DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).