dblp.uni-trier.dewww.uni-trier.de

Christos H. Papadimitriou Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
324EEChristos H. Papadimitriou: Algorithmic Game Theory: A Snapshot. ICALP (1) 2009: 3-11
323EEConstantinos Daskalakis, Christos H. Papadimitriou: On a Network Generalization of the Minmax Theorem. ICALP (2) 2009: 423-434
322EECatriel Beeri, Phokion G. Kolaitis, Christos H. Papadimitriou: The ACM PODS Alberto O. Mendelzon test-of-time-award 2009. PODS 2009: 43
321EEConstantinos Daskalakis, Christos H. Papadimitriou: On oblivious PTAS's for nash equilibrium. STOC 2009: 75-84
320EEElchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer: VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension CoRR abs/0905.1995: (2009)
319EEConstantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou: The complexity of computing a Nash equilibrium. Commun. ACM 52(2): 89-97 (2009)
318EEAnthony Spatharis, Ilias Foudalis, Martha Sideri, Christos H. Papadimitriou: Comparing Trade-off Based Models of the Internet. Fundam. Inform. 92(4): 363-372 (2009)
317EEParikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. SIAM J. Comput. 38(6): 2330-2355 (2009)
316EEConstantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou: A note on approximate Nash equilibria. Theor. Comput. Sci. 410(17): 1581-1588 (2009)
2008
315EEChristos H. Papadimitriou, Shuzhong Zhang: Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings Springer 2008
314EEConstantinos Daskalakis, Christos H. Papadimitriou: Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. FOCS 2008: 25-34
313EEChristos H. Papadimitriou, Michael Schapira, Yaron Singer: On the Hardness of Being Truthful. FOCS 2008: 250-259
312EETakehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno: On the Complexity of Reconfiguration Problems. ISAAC 2008: 28-39
311EEChristos H. Papadimitriou: The Search for Equilibrium Concepts. SAGT 2008: 1-3
310EEAlex Fabrikant, Christos H. Papadimitriou: The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. SODA 2008: 844-853
309EEHenry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou: Linked decompositions of networks and the power of choice in Polya urns. SODA 2008: 993-1002
308EEChristian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou: The myth of the folk theorem. STOC 2008: 365-372
307EEChristos H. Papadimitriou: Some Recent Results in Algorithmic Game Theory. WINE 2008: 17
306EEConstantinos Daskalakis, Christos H. Papadimitriou: Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games CoRR abs/0808.2801: (2008)
305EEChristos H. Papadimitriou, Tim Roughgarden: Computing correlated equilibria in multi-player games. J. ACM 55(3): (2008)
304EENikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani: Market equilibrium via a primal--dual algorithm for a convex program. J. ACM 55(5): (2008)
2007
303EEMoshe Babaioff, Robert Kleinberg, Christos H. Papadimitriou: Congestion games with malicious players. ACM Conference on Electronic Commerce 2007: 103-112
302EEConstantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou: Progress in approximate nash equilibria. ACM Conference on Electronic Commerce 2007: 355-358
301EEChristos H. Papadimitriou: Nash Equilibria: Where We Stand. ESA 2007: 1
300EEConstantinos Daskalakis, Christos H. Papadimitriou: Computing Equilibria in Anonymous Games. FOCS 2007: 83-93
299EELucian Popa, Afshin Rostamizadeh, Richard M. Karp, Christos H. Papadimitriou, Ion Stoica: Balancing traffic load in wireless networks with curveball routing. MobiHoc 2007: 170-179
298EEAlexander Hall, Evdokia Nikolova, Christos H. Papadimitriou: Incentive-Compatible Interdomain Routing with Linear Utilities. WINE 2007: 232-244
297EEChristos H. Papadimitriou: The Computation of Equilibria. WINE 2007: 5-6
296EEConstantinos Daskalakis, Christos H. Papadimitriou: Computing Equilibria in Anonymous Games CoRR abs/0710.5582: (2007)
295EEChristian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou: The Myth of the Folk Theorem. Electronic Colloquium on Computational Complexity (ECCC) 14(082): (2007)
294EEVladlen Koltun, Christos H. Papadimitriou: Approximately dominating representatives. Theor. Comput. Sci. 371(3): 148-154 (2007)
2006
293EEConstantinos Daskalakis, Christos H. Papadimitriou: Computing pure nash equilibria in graphical games via markov random fields. ACM Conference on Electronic Commerce 2006: 91-99
292EEParikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. ICALP (1) 2006: 346-357
291EEConstantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou: The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. ICALP (1) 2006: 513-524
290EEPaul W. Goldberg, Christos H. Papadimitriou: Reducibility among equilibrium problems. STOC 2006: 61-70
289EEConstantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou: The complexity of computing a Nash equilibrium. STOC 2006: 71-78
288EEConstantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou: A Note on Approximate Nash Equilibria. WINE 2006: 297-306
287EEZhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou: Recognizing Hole-Free 4-Map Graphs in Cubic Time. Algorithmica 45(2): 227-262 (2006)
286EEParikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies CoRR abs/cs/0609072: (2006)
285EEChristos H. Papadimitriou, Santosh Vempala: On The Approximability Of The Traveling Salesman Problem. Combinatorica 26(1): 101-120 (2006)
284EEParikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. Electronic Colloquium on Computational Complexity (ECCC) 13(094): (2006)
283EEMichal Feldman, Christos H. Papadimitriou, John Chuang, Ion Stoica: Free-riding and whitewashing in peer-to-peer systems. IEEE Journal on Selected Areas in Communications 24(5): 1010-1019 (2006)
282EEMilena Mihail, Christos H. Papadimitriou, Amin Saberi: On certain connectivity properties of the internet topology. J. Comput. Syst. Sci. 72(2): 239-251 (2006)
2005
281EEAlexander Hall, Christos H. Papadimitriou: Approximating the Distortion. APPROX-RANDOM 2005: 111-122
280EEChristos H. Papadimitriou: Games Other People Play. CONCUR 2005: 5
279EEChristos H. Papadimitriou: Algorithmic Problems in Ad Hoc Networks. DCOSS 2005: 1
278EEKonstantinos Daskalakis, Christos H. Papadimitriou: The Complexity of Games on Highly Regular Graphs. ESA 2005: 71-82
277EEVladlen Koltun, Christos H. Papadimitriou: Approximately Dominating Representatives. ICDT 2005: 204-214
276EEChristos H. Papadimitriou, Shmuel Safra: The complexity of low-distortion embeddings between point sets. SODA 2005: 112-118
275EEChristos H. Papadimitriou, Tim Roughgarden: Computing equilibria in multi-player games. SODA 2005: 82-91
274EEChristos H. Papadimitriou: Computing correlated equilibria in multi-player games. STOC 2005: 49-56
273EEChristos H. Papadimitriou: ... The Interaction Between Algorithms and Game Theory. WEA 2005: 1-3
272EEChristos H. Papadimitriou: Recent Developments in Equilibria Algorithms. WINE 2005: 1-2
271EEGeorgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri: Experiments with an Economic Model of the Worldwide Web. WINE 2005: 46-54
270EEGeorgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri: An economic model of the worldwide web. WWW (Special interest tracks and posters) 2005: 934-935
269EEJoan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker: A BGP-based mechanism for lowest-cost routing. Distributed Computing 18(1): 61-72 (2005)
268EEPaul W. Goldberg, Christos H. Papadimitriou: Reducibility Among Equilibrium Problems Electronic Colloquium on Computational Complexity (ECCC)(090): (2005)
267EEKonstantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou: The complexity of computing a Nash equilibrium Electronic Colloquium on Computational Complexity (ECCC)(115): (2005)
266EEKonstantinos Daskalakis, Christos H. Papadimitriou: Three-Player Games Are Hard Electronic Colloquium on Computational Complexity (ECCC)(139): (2005)
265EEChristos H. Papadimitriou, David Ratajczak: On a conjecture related to geometric routing. Theor. Comput. Sci. 344(1): 3-14 (2005)
2004
264EEChristos H. Papadimitriou, David Ratajczak: On a Conjecture Related to Geometric Routing. ALGOSENSORS 2004: 9-17
263EEChristos H. Papadimitriou: Networks and Games. HiPC 2004: 7
262EEJeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker: Global Synchronization in Sensornets. LATIN 2004: 609-624
261EEByung-Gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos H. Papadimitriou, John Kubiatowicz: Selfish caching in distributed systems: a game-theoretic analysis. PODC 2004: 21-30
260EEAlex Fabrikant, Christos H. Papadimitriou, Kunal Talwar: The complexity of pure Nash equilibria. STOC 2004: 604-612
259EEJon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan: Segmentation problems. J. ACM 51(2): 263-280 (2004)
2003
258EEChristos H. Papadimitriou: Games and Networks. FCT 2003: 157
257EEMilena Mihail, Christos H. Papadimitriou, Amin Saberi: On Certain Connectivity Properties of the Internet Topology. FOCS 2003: 28-35
256EEChristos H. Papadimitriou: Mythematics: storytelling in the teaching of computer science and mathematics. ITiCSE 2003: 1
255EEAnanth Rao, Christos H. Papadimitriou, Scott Shenker, Ion Stoica: Geographic routing without location information. MOBICOM 2003: 96-108
254 Christos H. Papadimitriou: The New Problems. PCK50 2003: 10
253EEAlex Fabrikant, Ankur Luthra, Elitza N. Maneva, Christos H. Papadimitriou, Scott Shenker: On a network creation game. PODC 2003: 347-351
252EEAaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos: An approximate truthful mechanism for combinatorial auctions with single parameter agents. SODA 2003: 205-214
251EERichard 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)
250EEGeorg Gottlob, Christos H. Papadimitriou: On the complexity of single-rule datalog queries. Inf. Comput. 183(1): 104-122 (2003)
249 Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos: An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents. Internet Mathematics 1(2): (2003)
248EEJon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan: Auditing Boolean attributes. J. Comput. Syst. Sci. 66(1): 244-253 (2003)
247EEXiaotie Deng, Christos H. Papadimitriou, Shmuel Safra: On the complexity of price equilibria. J. Comput. Syst. Sci. 67(2): 311-324 (2003)
246EEChristos H. Papadimitriou: MythematiCS: in praise of storytelling in the teaching of computer science and math. SIGCSE Bulletin 35(4): 7-9 (2003)
2002
245EEChristos H. Papadimitriou: Learning the Internet. COLT 2002: 396
244EENikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani: Market Equilibrium via a Primal-Dual-Type Algorithm. FOCS 2002: 389-395
243EEAlex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou: Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. ICALP 2002: 110-122
242EEChristos H. Papadimitriou: The Internet, the Web, and Algorithms. LATIN 2002: 2
241EEJoan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker: A BGP-based mechanism for lowest-cost routing. PODC 2002: 173-182
240EEMilena Mihail, Christos H. Papadimitriou: On the Eigenvalue Power Law. RANDOM 2002: 254-262
239EEChristos H. Papadimitriou: Understanding the Internet. SETN 2002: 1-2
238EEAditya 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
237EEChristos H. Papadimitriou: The Joy of Theory. STOC 2002: 116
236EEXiaotie Deng, Christos H. Papadimitriou, Shmuel Safra: On the complexity of equilibria. STOC 2002: 67-71
235EEJoseph 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)
234EEZhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou: Map graphs. J. ACM 49(2): 127-138 (2002)
233EEYannis E. Ioannidis, Christos H. Papadimitriou: Special Issue on PODS 1999 - Guest Editors' Foreword. J. Comput. Syst. Sci. 64(3): 441-442 (2002)
232 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)
2001
231 Christos H. Papadimitriou: Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. FOCS 2001: 4-8
230 Christos H. Papadimitriou: Algorithmic problems related to the Internet. HERCMA 2001: 92
229EEChristos H. Papadimitriou: Algorithms, Games, and the Internet. ICALP 2001: 1-3
228EEChristos H. Papadimitriou, Mihalis Yannakakis: Multiobjective Query Optimization. PODS 2001
227EEChristos H. Papadimitriou: Game theory, algorithms, and the Internet. SODA 2001: 391
226EEChristos H. Papadimitriou: Algorithms, games, and the internet. STOC 2001: 749-753
225 Pierluigi Crescenzi, Xiaotie Deng, Christos H. Papadimitriou: On Approximating a Scheduling Problem. J. Comb. Optim. 5(3): 287-297 (2001)
224 Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker: Sharing the Cost of Multicast Transmissions. J. Comput. Syst. Sci. 63(1): 21-41 (2001)
223EEVincent 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)
2000
222EEChristos H. Papadimitriou: Theoretical Problems Related to the Internet. COCOON 2000: 1-2
221 Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker: Optimization Problems in Congestion Control. FOCS 2000: 66-74
220 Christos H. Papadimitriou, Mihalis Yannakakis: On the Approximability of Trade-offs and Optimal Access of Web Sources. FOCS 2000: 86-92
219EEChristos H. Papadimitriou: On certain rigorous approaches to data mining (invited talk, abstract only). KDD 2000: 2
218EEJon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan: Auditing Boolean Attributes. PODS 2000: 86-91
217EEChristos H. Papadimitriou, Santosh Vempala: On the approximability of the traveling salesman problem (extended abstract). STOC 2000: 126-133
216EEJoan Feigenbaum, Christos H. Papadimitriou, Scott Shenker: Sharing the cost of muliticast transmissions (preliminary version). STOC 2000: 218-227
215 Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala: Latent Semantic Indexing: A Probabilistic Analysis. J. Comput. Syst. Sci. 61(2): 217-235 (2000)
214 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)
213 Elias Koutsoupias, Christos H. Papadimitriou: Beyond Competitive Analysis. SIAM J. Comput. 30(1): 300-317 (2000)
212 Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou: On the Difficulty of Designing Good Classifiers. SIAM J. Comput. 30(1): 318-323 (2000)
211EEKenneth A. Ross, Yannis E. Ioannidis, Anant Jhingran, Christos H. Papadimitriou: Reminiscences on Influential Papers. SIGMOD Record 29(4): 48-49 (2000)
1999
210EEGene 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
209EEDeborah Goldman, Sorin Istrail, Christos H. Papadimitriou: Algorithmic Aspects of Protein Structure Similarity. FOCS 1999: 512-522
208EEChristos H. Papadimitriou: Novel Computational Approaches to Information Retrieval and Data Mining (Abstract). ICDT 1999: 31
207EEGeorg Gottlob, Christos H. Papadimitriou: On the Complexity of Single-Rule Datalog Queries. LPAR 1999: 201-222
206EEChristos H. Papadimitriou: Topological Queries. SSD 1999: 3-4
205EEElias Koutsoupias, Christos H. Papadimitriou: Worst-case Equilibria. STACS 1999: 404-413
204EEZhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou: Map Graphs CoRR cs.DM/9910013: (1999)
203 Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. J. Comput. Syst. Sci. 58(1): 29-53 (1999)
202 Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. J. Comput. Syst. Sci. 58(3): 407-427 (1999)
201 Christos H. Papadimitriou, Martha Sideri: On the Floyd-Warshall Algorithm for Logic Programs. J. Log. Program. 41(1): 129-137 (1999)
200 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)
1998
199EEChristos H. Papadimitriou: Algorithmic Approaches to Information Retrieval and Data Mining (Abstract). COCOON 1998: 1
198EEChristos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala: Latent Semantic Indexing: A Probabilistic Analysis. PODS 1998: 159-168
197EEPierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis: On the complexity of protein folding (abstract). RECOMB 1998: 61-62
196EEJon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan: Segmentation Problems. STOC 1998: 473-482
195EEZhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou: Planar Map Graphs. STOC 1998: 514-523
194EEPierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis: On the Complexity of Protein Folding (Extended Abstract). STOC 1998: 597-603
193EEGoran Gogic, Christos H. Papadimitriou, Martha Sideri: Incremental Recompilation of Knowledge CoRR cs.AI/9801101: (1998)
192 Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan: A Microeconomic View of Data Mining. Data Min. Knowl. Discov. 2(4): 311-324 (1998)
191 Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu: Reflective Relational Machines. Inf. Comput. 143(2): 110-136 (1998)
190EEXiaotie Deng, Tiko Kameda, Christos H. Papadimitriou: How to Learn an Unknown Environment I: The Rectilinear Case. J. ACM 45(2): 215-245 (1998)
189EEGoran Gogic, Christos H. Papadimitriou, Martha Sideri: Incremental Recompilation of Knowledge. J. Artif. Intell. Res. (JAIR) 8: 23-37 (1998)
188 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)
1997
187 Christos H. Papadimitriou: Planar Topological Queries. CDB 1997: 1-6
186EEChristos H. Papadimitriou: NP-Completeness: A Retrospective. ICALP 1997: 2-6
185EEXiaotie Deng, Christos H. Papadimitriou: Decision-Making by Hierarchies of Discordant Agents. ISAAC 1997: 183-192
184EEChristos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997: 12-19
183EEJoseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256
182 Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou: Panarity, Revisited (Extended Abstract). WADS 1997: 472-473
181 Yannis Dimopoulos, Vangelis Magirou, Christos H. Papadimitriou: On Kernels, Defaults and Even Graphs. Ann. Math. Artif. Intell. 20(1-4): 1-12 (1997)
180 Christos H. Papadimitriou, Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. J. Comput. Syst. Sci. 54(1): 48-60 (1997)
1996
179 Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou: On the Difficulty of Designing Good Classifiers. COCOON 1996: 273-279
178EEChristos H. Papadimitriou: Computational Aspacts of Organization Theory (Extended Abstract). ESA 1996: 559-564
177EEElias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis: Searching a Fixed Graph. ICALP 1996: 280-289
176EEChristos H. Papadimitriou: The Complexity of Knowledge Representation. IEEE Conference on Computational Complexity 1996: 244-248
175EESerge Abiteboul, Gabriel M. Kuper, Christos H. Papadimitriou, Moshe Y. Vardi: In Memoriam: Paris C. Kanellakis. PODS 1996: 79
174EEChristos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92
173 Xiaotie Deng, Christos H. Papadimitriou: Competitive Distributed Decision-Making. Algorithmica 16(2): 133-150 (1996)
172EEElias Koutsoupias, Christos H. Papadimitriou: The 2-Evader Problem. Inf. Process. Lett. 57(5): 249-252 (1996)
171 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)
170 Christos H. Papadimitriou, Martha Sideri: The Bisection Width of Grid Graphs. Mathematical Systems Theory 29(2): 97-110 (1996)
1995
169 Michelangelo Grigni, Elias Koutsoupias, Christos H. Papadimitriou: An Approximation Scheme for Planar Graph TSP. FOCS 1995: 640-645
168 Goran Gogic, Henry A. Kautz, Christos H. Papadimitriou, Bart Selman: The Comparative Linguistics of Knowledge Representation. IJCAI (1) 1995: 862-869
167 Michelangelo Grigni, Dimitris Papadias, Christos H. Papadimitriou: Topological Inference. IJCAI (1) 1995: 901-907
166EEChristos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan: Optimal Information Delivery. ISAAC 1995: 181-187
165EEChristos H. Papadimitriou: Database Metatheory: Asking the Big Queries. PODS 1995: 1-10
164 Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan, Srihari Sampath Kumar: Multimedia Information Caching for Personalized Video-on-Demand. Computer Communications 18(3): 204-216 (1995)
163EEElias Koutsoupias, Christos H. Papadimitriou: On the k-Server Conjecture. J. ACM 42(5): 971-983 (1995)
162EEPierluigi Crescenzi, Christos H. Papadimitriou: Reversible Simulation of Space-Bounded Computations. Theor. Comput. Sci. 143(1): 159-165 (1995)
1994
161 Goran Gogic, Christos H. Papadimitriou, Martha Sideri: Incremental Recompilation of Knowledge. AAAI 1994: 922-927
160EEMilena Mihail, Christos H. Papadimitriou: On the Random Walk Method for Protocol Testing. CAV 1994: 132-141
159 Elias Koutsoupias, Christos H. Papadimitriou: Beyond Competitive Analysis FOCS 1994: 394-400
158 Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki: Motion Planning on a Graph (Extended Abstract) FOCS 1994: 511-520
157 Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan: Information Caching for Delivery of Personalized Video Programs on Home Entertainment Channels. ICMCS 1994: 214-223
156 Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu: The Power of Reflective Relational Machines LICS 1994: 230-240
155EEChristos H. Papadimitriou, Mihalis Yannakakis: On complexity as bounded rationality (extended abstract). STOC 1994: 726-733
154 Christos H. Papadimitriou, John N. Tsitsiklis: The Complexity of Optimal Queueing Network Control. Structure in Complexity Theory Conference 1994: 318-322
153 Christos H. Papadimitriou, P. Venkat Rangan, Martha Sideri: Designing Secure Communication Protocols from Trust Specification. Algorithmica 11(5): 485-499 (1994)
152 Christos H. Papadimitriou, Martha Sideri: Default Theories that Always Have Extensions. Artif. Intell. 69(1-2): 347-357 (1994)
151 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)
150 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)
1993
149EEDimitris J. Kavvadias, Christos H. Papadimitriou, Martha Sideri: On Horn Envelopes and Hypergraph Transversals. ISAAC 1993: 399-405
148EEChristos H. Papadimitriou, Mihalis Yannakakis: Linear programming without the matrix. STOC 1993: 121-129
147 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
146EEChristos H. Papadimitriou, Paolo Serafini, Mihalis Yannakakis: Computing the Throughput of a Network with Dedicated Lines. Discrete Applied Mathematics 42(2): 271-278 (1993)
145EEFoto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Logic Programs. J. ACM 40(4): 891-916 (1993)
1992
144EEChristos H. Papadimitriou, Martha Sideri: On Finding Extensions of Default Theories. ICDT 1992: 276-281
143 Xiaotie Deng, Christos H. Papadimitriou: Competitive Distributed Decision-Making. IFIP Congress (1) 1992: 350-356
142EEChristos H. Papadimitriou, Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. PODS 1992: 16-22
141 Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis: The Complexity of Multiway Cuts (Extended Abstract) STOC 1992: 241-251
140EEElias Koutsoupias, Christos H. Papadimitriou, Martha Sideri: On the Optimal Bisection of a Polygon. INFORMS Journal on Computing 4(4): 435-438 (1992)
139 Elias Koutsoupias, Christos H. Papadimitriou: On the Greedy Algorithm for Satisfiability. Inf. Process. Lett. 43(1): 53-55 (1992)
138 Christos H. Papadimitriou: The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem. SIAM J. Comput. 21(3): 450-465 (1992)
1991
137 Christos H. Papadimitriou: On Selecting a Satisfying Truth Assignment (Extended Abstract) FOCS 1991: 163-169
136 Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou: How to Learn an Unknown Environment (Extended Abstract) FOCS 1991: 298-303
135EEChristos H. Papadimitriou, P. Venkat Rangan, Martha Sideri: Designing Secure Communication Protocols from Trust Specifications. FSTTCS 1991: 360-368
134 Christos H. Papadimitriou: Decision-Making with Incomplete Information. ISA 1991: 1
133 Christos H. Papadimitriou, Mihalis Yannakakis: On the Value of Information in Distributed Decision-Making (Extended Abstract). PODC 1991: 61-64
132 Christos H. Papadimitriou, Martha Sideri: Optimal Coteries. PODC 1991: 75-80
131EEJoseph 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)
130EEEsther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis: Modularity of Cycles and Paths in Graphs. J. ACM 38(2): 255-274 (1991)
129 Phokion G. Kolaitis, Christos H. Papadimitriou: Why not Negation by Fixpoint? J. Comput. Syst. Sci. 43(1): 125-144 (1991)
128 Christos H. Papadimitriou, Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci. 43(3): 425-440 (1991)
127 Nimrod Megiddo, Christos H. Papadimitriou: On Total Functions, Existence Theorems and Computational Complexity. Theor. Comput. Sci. 81(2): 317-324 (1991)
126 Christos H. Papadimitriou, Mihalis Yannakakis: Shortest Paths Without a Map. Theor. Comput. Sci. 84(1): 127-150 (1991)
1990
125 Xiaotie Deng, Christos H. Papadimitriou: Exploring an Unknown Graph (Extended Abstract) FOCS 1990: 355-361
124 Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis: On the Predictability of Coupled Automata: An Allegory about Chaos FOCS 1990: 788-793
123 Christos H. Papadimitriou: On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract) FOCS 1990: 794-801
122 Christos H. Papadimitriou, Martha Sideri: The Bisection Width of Grid Graphs. SODA 1990: 405-410
121 Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis: On the Complexity of Local Search (Extended Abstract) STOC 1990: 438-445
120EEElias Koutsoupias, Christos H. Papadimitriou, Martha Sideri: On the Optimal Bisection of a Polygon (Extended Abstract). Symposium on Computational Geometry 1990: 198-202
119 Dimitris J. Kavvadias, Christos H. Papadimitriou: A Linear Programming Approach to Reasoning about Probabilities. Ann. Math. Artif. Intell. 1: (1990)
118 Christos H. Papadimitriou, Mihalis Yannakakis: On recognizing integer polyhedra. Combinatorica 10(1): 107-109 (1990)
117 Xanthippi Markenscoff, Luqun Ni, Christos H. Papadimitriou: The Geometry of Grasping. I. J. Robotic Res. 9(1): 61-74 (1990)
116 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)
115EEPhokion G. Kolaitis, Christos H. Papadimitriou: Some Computational Aspects of Circumscription J. ACM 37(1): 1-14 (1990)
114 Christos H. Papadimitriou, Mihalis Yannakakis: Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput. 19(2): 322-328 (1990)
1989
113EEChristos H. Papadimitriou, Mihalis Yannakakis: Shortest Paths Without a Map. ICALP 1989: 610-620
112 Xanthippi Markenscoff, Christos H. Papadimitriou: Optimum Grip of a Polygon. I. J. Robotic Res. 8(2): 17-29 (1989)
111 Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou: Corrigendum: The Complexity of Cubical Graphs Inf. Comput. 82(3): 350-353 (1989)
110 Ellen B. Feinberg, Christos H. Papadimitriou: Finding Feasible Paths for a Two-Point Body. J. Algorithms 10(1): 109-119 (1989)
109EEMichael D. Hirsch, Christos H. Papadimitriou, Stephen A. Vavasis: Exponential lower bounds for finding Brouwer fix points. J. Complexity 5(4): 379-416 (1989)
108 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)
1988
107 Phokion G. Kolaitis, Christos H. Papadimitriou: Some Computational Aspects of Circumscription. AAAI 1988: 455-469
106 Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou: Scheduling Dags to Minimize Time and Communication. AWOC 1988: 134-138
105EEPhokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239
104 Christos H. Papadimitriou, Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes (Extended Abstract) STOC 1988: 229-234
103 Christos H. Papadimitriou, Mihalis Yannakakis: Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract) STOC 1988: 510-513
102 Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou: The Synthesis of Communication Protocols. Algorithmica 3: 451-472 (1988)
101 Sophocles Ephremidis, Christos H. Papadimitriou, Martha Sideri: Complexity Characterizations of Attribute Grammar Languages Inf. Comput. 78(3): 178-186 (1988)
100 David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: On Generating All Maximal Independent Sets. Inf. Process. Lett. 27(3): 119-123 (1988)
99EENimrod 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)
98EEGeorge F. Georgakopoulos, Dimitris J. Kavvadias, Christos H. Papadimitriou: Probabilistic satisfiability. J. Complexity 4(1): 1-11 (1988)
97 Lefteris M. Kirousis, Christos H. Papadimitriou: The Complexity of Recognizing Polyhedral Scenes. J. Comput. Syst. Sci. 37(1): 14-38 (1988)
96 Christos H. Papadimitriou, David Wolfe: The Complexity of Facets Resolved. J. Comput. Syst. Sci. 37(1): 2-13 (1988)
95 David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy is Local Search? J. Comput. Syst. Sci. 37(1): 79-100 (1988)
1987
94EEFoto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213
93EEJoseph S. B. Mitchell, Christos H. Papadimitriou: The Weighted Region Problem. Symposium on Computational Geometry 1987: 30-38
92 Christos H. Papadimitriou, Ellen B. Silverberg: Optimal Piecewise Linear Motion of an Object Among Obstacles. Algorithmica 2: 523-539 (1987)
91 George K. Georgakopoulos, Christos H. Papadimitriou: The 1-Steiner Tree Problem. J. Algorithms 8(1): 122-130 (1987)
90 Christos H. Papadimitriou, John N. Tsitsiklis: On Stochastic Scheduling with In-Tree Precedence Constraints. SIAM J. Comput. 16(1): 1-6 (1987)
89 Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Reliable Concurrency Control. SIAM J. Comput. 16(3): 538-553 (1987)
88 Christos H. Papadimitriou, Jeffrey D. Ullman: A Communication-Time Tradeoff. SIAM J. Comput. 16(4): 639-646 (1987)
87 Joseph S. B. Mitchell, David M. Mount, Christos H. Papadimitriou: The Discrete Geodesic Problem. SIAM J. Comput. 16(4): 647-668 (1987)
1986
86 Christos H. Papadimitriou: The Theory of Database Concurrency Control Computer Science Press 1986
85EEChristos H. Papadimitriou: Shortest-Path Motion. FSTTCS 1986: 144-153
84 Foto N. Afrati, Christos H. Papadimitriou, Georgios I. Papadimitriou: The Synthesis of Communication Protocols. PODC 1986: 263-271
83EEFoto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman: Convergence of Sideways Query Evaluation. PODS 1986: 24-30
82 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)
81 Christos H. Papadimitriou, Mihalis Yannakakis: A Note on Succinct Representations of Graphs Information and Control 71(3): 181-185 (1986)
80EEJohn N. Tsitsiklis, Christos H. Papadimitriou, Pierre A. Humblet: The performance of a precedence-based queuing discipline. J. ACM 33(3): 593-602 (1986)
79 Esther M. Arkin, Christos H. Papadimitriou: On the Complexity of Circulations. J. Algorithms 7(1): 134-145 (1986)
78 Thanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. J. Comput. Syst. Sci. 33(2): 297-310 (1986)
77 Lefteris M. Kirousis, Christos H. Papadimitriou: Searching and Pebbling. Theor. Comput. Sci. 47(3): 205-218 (1986)
1985
76 Lefteris M. Kirousis, Christos H. Papadimitriou: The Complexity of Recognizing Polyhedral Scenes (Extended Abstract) FOCS 1985: 175-185
75 David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy Is Local Search? (Extended Abstract) FOCS 1985: 39-42
74 Christos H. Papadimitriou, David Wolfe: The Complexity of Facets Resolved FOCS 1985: 74-78
73EEChristos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Reliable Concurrency Control. PODS 1985: 230-234
72EEThanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. PODS 1985: 96-104
71 Christos H. Papadimitriou: A note the expressive power of Prolog. Bulletin of the EATCS 26: 21-22 (1985)
70EELefteris M. Kirousis, Christos H. Papadimitriou: Interval graphs and seatching. Discrete Mathematics 55(2): 181-184 (1985)
69 Christos H. Papadimitriou: An Algorithm for Shortest-Path Motion in Three Dimensions. Inf. Process. Lett. 20(5): 259-263 (1985)
68 Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou: The Complexity of Cubical Graphs Information and Control 66(1/2): 53-60 (1985)
67EEChristos H. Papadimitriou: Correction to ``A Theorem in Database Concurrency Control'' J. ACM 32(3): 750 (1985)
66 Christos H. Papadimitriou: Games Against Nature. J. Comput. Syst. Sci. 31(2): 288-301 (1985)
65 Paris C. Kanellakis, Christos H. Papadimitriou: The Complexity of Distributed Concurrency Control. SIAM J. Comput. 14(1): 52-74 (1985)
1984
64 Christos H. Papadimitriou, Jeffrey D. Ullman: A Communication-Time Tradeoff FOCS 1984: 84-88
63EEFoto N. Afrati, Christos H. Papadimitriou, George Papageorgiou: The Complexity of Cubical Graphs (Extended Abstract). ICALP 1984: 51-57
62EEChristos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9(1): 89-99 (1984)
61EEChristos H. Papadimitriou: On the complexity of unique solutions. J. ACM 31(2): 392-400 (1984)
60EEStavros S. Cosmadakis, Christos H. Papadimitriou: Updates of Relational Views. J. ACM 31(4): 742-760 (1984)
59 Christos H. Papadimitriou, Umesh V. Vazirani: On Two Geometric Problems Related to the Traveling Salesman Problem. J. Algorithms 5(2): 231-246 (1984)
58 Paris C. Kanellakis, Christos H. Papadimitriou: Is Distributed Locking Harder? J. Comput. Syst. Sci. 28(1): 103-120 (1984)
57 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)
56 Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). J. Comput. Syst. Sci. 28(2): 244-259 (1984)
55 Christos H. Papadimitriou, Michael Sipser: Communication Complexity. J. Comput. Syst. Sci. 28(2): 260-269 (1984)
54 Stavros S. Cosmadakis, Christos H. Papadimitriou: The Traveling Salesman Problem with Many Visits to Few Cities. SIAM J. Comput. 13(1): 99-108 (1984)
1983
53EEFillia Makedon, Christos H. Papadimitriou, Ivan Hal Sudborough: Topological Bandwidth. CAAP 1983: 317-331
52 Christos H. Papadimitriou: Games Against Nature (Extended Abstract) FOCS 1983: 446-450
51EEMihalis 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
50EEStavros S. Cosmadakis, Christos H. Papadimitriou: Updates of Relational Views. PODS 1983: 317-331
49 Christos H. Papadimitriou, Stathis Zachos: Two remarks on the power of counting. Theoretical Computer Science 1983: 269-276
48 Christos H. Papadimitriou: Theory of concurrency control. Theoretical Computer Science 1983: 35-47
47 H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. Acta Inf. 19: 1-11 (1983)
46 Christos H. Papadimitriou: Concurrency Control by Locking. SIAM J. Comput. 12(2): 215-226 (1983)
1982
45 Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity Prentice-Hall 1982
44 Christos H. Papadimitriou: On the Complexity of Unique Solutions FOCS 1982: 14-20
43EEMarco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176
42EEChristos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. PODS 1982: 76-82
41EEParis C. Kanellakis, Christos H. Papadimitriou: Is Distributed Locking Harder? PODS 1982: 98-107
40 Christos H. Papadimitriou, Michael Sipser: Communication Complexity STOC 1982: 196-200
39 Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity) STOC 1982: 255-260
38 Christos H. Papadimitriou, John N. Tsitsiklis: On the Complexity of Designing Distributed Protocols Information and Control 53(3): 211-218 (1982)
37EEChristos H. Papadimitriou, Mihalis Yannakakis: The complexity of restricted spanning tree problems. J. ACM 29(2): 285-309 (1982)
36EEChristos H. Papadimitriou: A theorem in database concurrency control. J. ACM 29(4): 998-1006 (1982)
35 Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41 (1982)
34 Richard M. Karp, Christos H. Papadimitriou: On Linear Characterizations of Combinatorial Optimization Problems. SIAM J. Comput. 11(4): 620-632 (1982)
33 Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Paths in Grid Graphs. SIAM J. Comput. 11(4): 676-686 (1982)
32 Harry R. Lewis, Christos H. Papadimitriou: Symmetric Space-Bounded Computation. Theor. Comput. Sci. 19: 161-187 (1982)
1981
31 Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation Prentice-Hall 1981
30 Paris C. Kanellakis, Christos H. Papadimitriou: The Complexity of Distributed Concurrency Control FOCS 1981: 185-197
29 Christos H. Papadimitriou, Mihalis Yannakakis: Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract) FOCS 1981: 358-363
28 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
27EEChristos H. Papadimitriou: On the Power of Locking. SIGMOD Conference 1981: 148-154
26 Christos H. Papadimitriou, Mihalis Yannakakis: On Minimal Eulerian Graphs. Inf. Process. Lett. 12(4): 203-205 (1981)
25 Christos H. Papadimitriou, Mihalis Yannakakis: The Clique Problem for Planar Graphs. Inf. Process. Lett. 13(4/5): 131-133 (1981)
24 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)
23EEChristos H. Papadimitriou: On the complexity of integer programming. J. ACM 28(4): 765-768 (1981)
22 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)
21 Christos H. Papadimitriou: Worst-Case and Probabilistic Analysis of a Geometric Location Problem. SIAM J. Comput. 10(3): 542-557 (1981)
20 Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael Rodeh: Covering Graphs by Simple Circuits. SIAM J. Comput. 10(4): 746-750 (1981)
1980
19 Richard M. Karp, Christos H. Papadimitriou: On Linear Characterizations of Combinatorial Optimization Problems FOCS 1980: 1-9
18 Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract) FOCS 1980: 328-332
17EEHarry R. Lewis, Christos H. Papadimitriou: Symmetric Space-Bounded Computation (Extended Abstract). ICALP 1980: 374-384
16EEChristos H. Papadimitriou, Jon Louis Bentley: A Worst-Case Analysis of Nearest Neighbor Searching by Projection. ICALP 1980: 470-482
15EEChristos 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)
14EEChristos H. Papadimitriou, Paris C. Kanellakis: Flowshop scheduling with limited temporary storage. J. ACM 27(3): 533-549 (1980)
1979
13 Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung: Locking Policies: Safety and Freedom from Deadlock FOCS 1979: 286-297
12EEChristos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). ICALP 1979: 460-470
11EEH. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126
10 Christos H. Papadimitriou: Efficient Search for Rationals. Inf. Process. Lett. 8(1): 1-4 (1979)
9EEChristos H. Papadimitriou: Optimality of the Fast Fourier transform. J. ACM 26(1): 95-102 (1979)
8EEChristos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653 (1979)
7 Christos H. Papadimitriou, Mihalis Yannakakis: Scheduling Interval-Ordered Tasks. SIAM J. Comput. 8(3): 405-409 (1979)
1978
6 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)
1977
5 Christos H. Papadimitriou, Kenneth Steiglitz: On the Complexity of Local Search for the Traveling Salesman Problem. SIAM J. Comput. 6(1): 76-83 (1977)
4 Christos H. Papadimitriou: The Euclidean Traveling Salesman Problem is NP-Complete. Theor. Comput. Sci. 4(3): 237-244 (1977)
1976
3 Christos H. Papadimitriou, Kenneth Steiglitz: Some Complexity Results for the Traveling Salesman Problem STOC 1976: 1-9
2EEChristos H. Papadimitriou: The NP-Completeness of the bandwidth minimization problem. Computing 16(3): 263-270 (1976)
1EEChristos H. Papadimitriou: On the complexity of edge traversing. J. ACM 23(3): 544-554 (1976)

Coauthor Index

1Serge Abiteboul [156] [175] [191]
2Foto N. Afrati [63] [68] [82] [83] [84] [94] [102] [106] [108] [111] [145]
3Aditya Akella [238]
4Christos Amanatidis [309]
5Aaron Archer [249] [252]
6Esther M. Arkin [79] [130]
7Moshe Babaioff [303]
8Marco Barreno [261]
9Catriel Beeri [322]
10Jon Louis Bentley [16]
11Philip A. Bernstein [6] [15]
12Vincent D. Blondel [223]
13Manuel Blum [24]
14Christian Borgs [295] [308]
15Olivier Bournez [223]
16Samuel R. Buss [124]
17Marco A. Casanova [43] [57]
18Kamalika Chaudhuri [261]
19Jennifer T. Chayes [295] [308]
20Zhi-Zhong Chen [182] [195] [204] [234] [287]
21Gene Cheung [210]
22John C.-I. Chuang (John Chuang) [283]
23Byung-Gon Chun [261]
24Stavros S. Cosmadakis [50] [51] [54] [60] [82]
25Pierluigi Crescenzi (Pilu Crescenzi) [162] [188] [194] [197] [225]
26Elias Dahlhaus [141] [150]
27Evgeny Dantsin [232]
28Constantinos Daskalakis (Konstantinos Daskalakis) [266] [267] [278] [288] [289] [291] [293] [296] [300] [302] [306] [314] [316] [319] [321] [323]
29Erik D. Demaine [312]
30Xiaotie Deng [125] [136] [143] [173] [185] [190] [225] [236] [247]
31Richard Desper [200] [214]
32Nikhil R. Devanur [244] [304]
33Yannis Dimopoulos [181]
34Jeremy Elson [262]
35Sophocles Ephremidis [101]
36Alex Fabrikant [243] [253] [260] [291] [310]
37Ronald Fagin [43] [57]
38Joan Feigenbaum [216] [224] [241] [269]
39Ellen B. Feinberg [110]
40Michal Feldman [283]
41Ilias Foudalis [318]
42M. R. Garey (Michael R. Garey) [28] [99]
43George F. Georgakopoulos [98]
44George K. Georgakopoulos [91]
45Andreas Goerdt [232]
46Goran Gogic [161] [168] [189] [193]
47Paul W. Goldberg [267] [268] [289] [290] [319]
48Deborah Goldman [188] [194] [197] [209]
49Nathan Goodman [6]
50Parikshit Gopalan [284] [286] [292] [317]
51Georg Gottlob [207] [250]
52Michelangelo Grigni [167] [169] [179] [182] [195] [204] [212] [234] [287]
53Thanasis Hadzilacos [72] [78]
54S. Louis Hakimi [28] [99]
55Alexander Hall [281] [298]
56Nicholas J. A. Harvey [312]
57Joseph M. Hellerstein [183] [235]
58Edward A. Hirsch [232]
59Michael D. Hirsch [109]
60Pierre A. Humblet [80]
61Nicole Immorlica [295] [308]
62Yannis E. Ioannidis [211] [233]
63Sorin Istrail [209]
64Alon Itai [20] [33]
65Takehiro Ito [312]
66Anant Jhingran [211]
67Feng Jiang [200] [214]
68David S. Johnson [28] [75] [95] [99] [100] [141] [150]
69Adam Tauman Kalai (Adam Kalai) [295] [308]
70Olli-P. Kallioniemi [200] [214]
71Tiko Kameda [136] [190]
72Paris C. Kanellakis [14] [30] [41] [42] [51] [58] [62] [65]
73Ravi Kannan (Ravindran Kannan) [232]
74Richard M. Karp [19] [24] [34] [221] [238] [251] [262] [299] [309]
75Henry A. Kautz [168]
76Dimitris J. Kavvadias [98] [119] [149]
77Lefteris M. Kirousis [70] [76] [77] [97]
78Jon M. Kleinberg [192] [196] [218] [232] [248] [259]
79Robert D. Kleinberg (Robert Kleinberg) [303]
80Pascal Koiran [223]
81Phokion G. Kolaitis [105] [107] [115] [129] [284] [286] [292] [317] [322]
82John G. Kollias [116]
83Vladlen Koltun [277] [294]
84Georgios Kouroupas [270] [271]
85Elias Koutsoupias [120] [139] [140] [159] [163] [169] [172] [177] [183] [205] [213] [221] [235] [243] [270] [271]
86John Kubiatowicz [261]
87Srihari Sampath Kumar [164]
88H. T. Kung [11] [13] [47]
89Gabriel M. Kuper [175]
90Harry R. Lewis [17] [31] [32]
91Henry C. Lin [309]
92Witold Lipski Jr. [22]
93Richard J. Lipton [20]
94Ankur Luthra [253]
95Vangelis Magirou [181]
96Fillia Makedon [53]
97Elitza N. Maneva [253] [284] [286] [292] [317]
98Yannis Manolopoulos [116]
99Xanthippi Markenscoff [112] [117]
100Steven McCanne [210]
101Nimrod Megiddo [28] [99] [127]
102Aranyak Mehta [288] [302] [316]
103Milena Mihail [160] [240] [257] [282]
104Daniel P. Miranker (Dan Miranker) [235]
105Vincent Mirelli [179] [212]
106Vahab S. Mirrokni (Seyed Vahab Mirrokni) [295] [308]
107Joseph S. B. Mitchell [87] [93] [131]
108Holger Moch [200] [214]
109Elchanan Mossel [320]
110David M. Mount [87]
111Luqun Ni [117]
112Evdokia Nikolova [298]
113Dimitris Papadias [167]
114Georgios I. Papadimitriou [84]
115George Papageorgiou [63] [68] [82] [83] [102] [106] [108] [111]
116Nadia Papakostantinou [82]
117Antonio Piccolboni [188] [194] [197]
118Lucian Popa [299]
119Prabhakar Raghavan [158] [192] [196] [198] [215] [218] [232] [248] [259]
120Srinivas Ramanathan [157] [164] [166]
121P. Venkat Rangan [135] [153] [157] [164] [166]
122Ananth Rao [255]
123David Ratajczak [264] [265]
124Michael Rodeh [20]
125Kenneth A. Ross [211]
126Afshin Rostamizadeh [299]
127James B. Rothnie Jr. [6]
128Tim Roughgarden [275] [305]
129Athena Roussou [83] [108]
130Amin Saberi [244] [257] [282] [304]
131Shmuel Safra [236] [247] [276]
132Yehoshua Sagiv [83] [108]
133Rahul Sami [241] [269]
134Vasilis Samoladas [235]
135Alejandro A. Schäffer [121] [200] [214]
136Michael Schapira [313] [320]
137Uwe Schöning [232]
138Bart Selman [168]
139Paolo Serafini [146]
140Srinivasan Seshan [238]
141Paul D. Seymour [141] [150]
142Scott Shenker [216] [221] [224] [238] [241] [251] [253] [255] [262] [269]
143Martha Sideri [101] [120] [122] [132] [135] [140] [144] [149] [152] [153] [161] [170] [189] [193] [201] [270] [271] [309] [312] [318]
144Ellen B. Silverberg [92]
145Yaron Singer [313] [320]
146Michael Sipser [40] [55]
147Anthony Spatharis [318]
148Kenneth Steiglitz [3] [5] [45]
149Ion Stoica [255] [283] [299]
150Dan Suciu [174] [203]
151Madhu Sudan [158]
152Ivan Hal Sudborough [53]
153Jayme Luiz Szwarcfiter [33]
154Kunal Talwar [249] [252] [260]
155Hisao Tamaki [158] [198] [215]
156Éva Tardos [249] [252]
157John N. Tsitsiklis [38] [80] [90] [124] [154] [223]
158Ryuhei Uehara [312]
159Jeffrey D. Ullman [64] [83] [88] [108]
160Yushi Uno [312]
161Moshe Y. Vardi [175]
162Stephen A. Vavasis [109]
163Umesh V. Vazirani [59]
164Vijay V. Vazirani [244] [304]
165Santosh Vempala [198] [215] [217] [285]
166Victor Vianu [156] [174] [191] [203]
167Oliver Vornberger [24]
168Hoeteck Wee [261]
169David Wolfe [74] [96]
170Mihalis Yannakakis [7] [12] [13] [18] [24] [25] [26] [29] [35] [37] [39] [51] [56] [73] [75] [81] [89] [95] [100] [103] [104] [113] [114] [118] [121] [126] [128] [130] [133] [141] [142] [146] [147] [148] [150] [155] [171] [177] [180] [184] [188] [194] [197] [202] [220] [228]
171Stathis Zachos [49]
172Shuzhong Zhang [315]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)