Christos H. Papadimitriou

Bing Citeseer DBLP Google Google Scholar Kosmix Wikipedia Yahoo!
Loading Google Thumbnails...
2011
339Economies with non-convex production and complexity equilibria. Christos H. Papadimitriou, Christopher A. Wilkens. ACM Conference on Electronic Commerce 2011, 137-146. Web SearchBibTeXDownload
338Mechanisms for complement-free procurement. Shahar Dobzinski, Christos H. Papadimitriou, Yaron Singer. ACM Conference on Electronic Commerce 2011, 273-282. Web SearchBibTeXDownload
337On Oblivious PTAS's for Nash Equilibrium. Constantinos Daskalakis, Christos H. Papadimitriou. CoRR (abs/1102.2280) (2011). Web SearchBibTeXDownload
336The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani. FOCS 2011, 67-76. Web SearchBibTeXDownload
335Continuous Local Search. Constantinos Daskalakis, Christos H. Papadimitriou. SODA 2011, 790-804. Web SearchBibTeXDownload
334On optimal single-item auctions. Christos H. Papadimitriou, George Pierrakos. STOC 2011, 119-128. Web SearchBibTeXDownload
333On the complexity of reconfiguration problems. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno. Theor. Comput. Sci. (412): 1054-1065 (2011). Web SearchBibTeXDownload
332Modeling Social Networks through User Background and Behavior. Ilias Foudalis, Kamal Jain, Christos H. Papadimitriou, Martha Sideri. WAW 2011, 85-102. Web SearchBibTeXDownload
331Games, algorithms, and the Internet. Christos H. Papadimitriou. WWW 2011, 5-6. Web SearchBibTeXDownload
2010
330The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani. CoRR (abs/1006.5352) (2010). Web SearchBibTeXDownload
329On Optimal Single-Item Auctions. Christos H. Papadimitriou, George Pierrakos. CoRR (abs/1011.1279) (2010). Web SearchBibTeXDownload
328Budget Feasible Mechanisms. Christos H. Papadimitriou, Yaron Singer. CoRR (abs/1002.2334) (2010). Web SearchBibTeXDownload
327A New Look at Selfish Routing. Christos H. Papadimitriou, Gregory Valiant. ICS 2010, 178-187. Web SearchBibTeXDownload
326On Learning Algorithms for Nash Equilibria. Constantinos Daskalakis, Rafael Frongillo, Christos H. Papadimitriou, George Pierrakos, Gregory Valiant. SAGT 2010, 114-125. Web SearchBibTeXDownload
325When the Players Are Not Expectation Maximizers. Amos Fiat, Christos H. Papadimitriou. SAGT 2010, 1-14. Web SearchBibTeXDownload
324Inapproximability for VCG-Based Combinatorial Auctions. David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans. SODA 2010, 518-536. Web SearchBibTeXDownload
2009
323The complexity of computing a Nash equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. Commun. ACM (52): 89-97 (2009). Web SearchBibTeXDownload
322Worst-case equilibria. Elias Koutsoupias, Christos H. Papadimitriou. Computer Science Review (3): 65-69 (2009). Web SearchBibTeXDownload
321VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension. Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer. CoRR (abs/0905.1995) (2009). Web SearchBibTeXDownload
320Comparing Trade-off Based Models of the Internet. Anthony Spatharis, Ilias Foudalis, Martha Sideri, Christos H. Papadimitriou. Fundam. Inform. (92): 363-372 (2009). Web SearchBibTeXDownload
319Algorithmic Game Theory: A Snapshot. Christos H. Papadimitriou. ICALP (1) 2009, 3-11. Web SearchBibTeXDownload
318On a Network Generalization of the Minmax Theorem. Constantinos Daskalakis, Christos H. Papadimitriou. ICALP (2) 2009, 423-434. Web SearchBibTeXDownload
317The ACM PODS Alberto O. Mendelzon test-of-time-award 2009. Catriel Beeri, Phokion G. Kolaitis, Christos H. Papadimitriou. PODS 2009, 43. Web SearchBibTeXDownload
316The Complexity of Computing a Nash Equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. SIAM J. Comput. (39): 195-259 (2009). Web SearchBibTeXDownload
315The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou. SIAM J. Comput. (38): 2330-2355 (2009). Web SearchBibTeXDownload
314On oblivious PTAS's for nash equilibrium. Constantinos Daskalakis, Christos H. Papadimitriou. STOC 2009, 75-84. Web SearchBibTeXDownload
313A note on approximate Nash equilibria. Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou. Theor. Comput. Sci. (410): 1581-1588 (2009). Web SearchBibTeXDownload
312A Note on Strictly Competitive Games. Ilan Adler, Constantinos Daskalakis, Christos H. Papadimitriou. WINE 2009, 471-474. Web SearchBibTeXDownload
2008
311On the Hardness of Being Truthful. Christos H. Papadimitriou, Michael Schapira, Yaron Singer. FOCS 2008, 250-259. Web SearchBibTeXDownload
310Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. Constantinos Daskalakis, Christos H. Papadimitriou. FOCS (abs/0808.2801): 25-34 (2008). Web SearchBibTeXDownload
309Incentive-Compatible Interdomain Routing with Linear Utilities. Alexander Hall, Evdokia Nikolova, Christos H. Papadimitriou. Internet Mathematics (5): 395-410 (2008). Web SearchBibTeXDownload
308On the Complexity of Reconfiguration Problems. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno. ISAAC 2008, 28-39. Web SearchBibTeXDownload
307Computing correlated equilibria in multi-player games. Christos H. Papadimitriou, Tim Roughgarden. J. ACM (55) (2008). Web SearchBibTeXDownload
306Market equilibrium via a primal--dual algorithm for a convex program. Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani. J. ACM (55) (2008). Web SearchBibTeXDownload
305The Search for Equilibrium Concepts. Christos H. Papadimitriou. SAGT 2008, 1-3. Web SearchBibTeXDownload
304The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. Alex Fabrikant, Christos H. Papadimitriou. SODA 2008, 844-853. Web SearchBibTeXDownload
303Linked decompositions of networks and the power of choice in Polya urns. Henry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou. SODA 2008, 993-1002. Web SearchBibTeXDownload
302The myth of the folk theorem. Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou. STOC 2008, 365-372. Web SearchBibTeXDownload
301Some Recent Results in Algorithmic Game Theory. Christos H. Papadimitriou. WINE 2008, 17. Web SearchBibTeXDownload
2007
300Progress in approximate nash equilibria. Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou. ACM Conference on Electronic Commerce 2007, 355-358. Web SearchBibTeXDownload
299Congestion games with malicious players. Moshe Babaioff, Robert Kleinberg, Christos H. Papadimitriou. ACM Conference on Electronic Commerce 2007, 103-112. Web SearchBibTeXDownload
298The Myth of the Folk Theorem. Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou. Electronic Colloquium on Computational Complexity (ECCC) (14) (2007). Web SearchBibTeXDownload
297Nash Equilibria: Where We Stand. Christos H. Papadimitriou. ESA 2007, 1. Web SearchBibTeXDownload
296Computing Equilibria in Anonymous Games. Constantinos Daskalakis, Christos H. Papadimitriou. FOCS 2007, 83-93. Web SearchBibTeXDownload
295Balancing traffic load in wireless networks with curveball routing. Lucian Popa, Afshin Rostamizadeh, Richard M. Karp, Christos H. Papadimitriou, Ion Stoica. MobiHoc 2007, 170-179. Cited by 30Web SearchBibTeXDownload
294Approximately dominating representatives. Vladlen Koltun, Christos H. Papadimitriou. Theor. Comput. Sci. (371): 148-154 (2007). Web SearchBibTeXDownload
293Incentive-Compatible Interdomain Routing with Linear Utilities. Alexander Hall, Evdokia Nikolova, Christos H. Papadimitriou. WINE 2007, 232-244. Web SearchBibTeXDownload
292The Computation of Equilibria. Christos H. Papadimitriou. WINE 2007, 5-6. Web SearchBibTeXDownload
2006
291Computing pure nash equilibria in graphical games via markov random fields. Constantinos Daskalakis, Christos H. Papadimitriou. ACM Conference on Electronic Commerce 2006, 91-99. Web SearchBibTeXDownload
290Recognizing Hole-Free 4-Map Graphs in Cubic Time. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. Algorithmica (45): 227-262 (2006). Web SearchBibTeXDownload
289On The Approximability Of The Traveling Salesman Problem. Christos H. Papadimitriou, Santosh Vempala. Combinatorica (26): 101-120 (2006). Web SearchBibTeXDownload
288The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou. ICALP (1) 2006, 513-524. Web SearchBibTeXDownload
287The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou. ICALP (1) 2006, 346-357. Web SearchBibTeXDownload
286Free-riding and whitewashing in peer-to-peer systems. Michal Feldman, Christos H. Papadimitriou, John Chuang, Ion Stoica. IEEE Journal on Selected Areas in Communications (24): 1010-1019 (2006). Web SearchBibTeXDownload
285On certain connectivity properties of the internet topology. Milena Mihail, Christos H. Papadimitriou, Amin Saberi. J. Comput. Syst. Sci. (72): 239-251 (2006). Web SearchBibTeXDownload
284Reducibility among equilibrium problems. Paul W. Goldberg, Christos H. Papadimitriou. STOC 2006, 61-70. Web SearchBibTeXDownload
283The complexity of computing a Nash equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. STOC 2006, 71-78. Web SearchBibTeXDownload
282A Note on Approximate Nash Equilibria. Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou. WINE 2006, 297-306. Web SearchBibTeXDownload
2005
281Approximating the Distortion. Alexander Hall, Christos H. Papadimitriou. APPROX-RANDOM 2005, 111-122. Web SearchBibTeXDownload
280Games Other People Play. Christos H. Papadimitriou. CONCUR 2005, 5. Web SearchBibTeXDownload
279Algorithmic Problems in Ad Hoc Networks. Christos H. Papadimitriou. DCOSS 2005, 1. Web SearchBibTeXDownload
278A BGP-based mechanism for lowest-cost routing. Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker. Distributed Computing (18): 61-72 (2005). Web SearchBibTeXDownload
277The complexity of computing a Nash equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. Electronic Colloquium on Computational Complexity (ECCC) 2005. Web SearchBibTeXDownload
276Reducibility Among Equilibrium Problems. Paul W. Goldberg, Christos H. Papadimitriou. Electronic Colloquium on Computational Complexity (ECCC) 2005. Web SearchBibTeXDownload
275Three-Player Games Are Hard. Konstantinos Daskalakis, Christos H. Papadimitriou. Electronic Colloquium on Computational Complexity (ECCC) 2005. Web SearchBibTeXDownload
274The Complexity of Games on Highly Regular Graphs. Konstantinos Daskalakis, Christos H. Papadimitriou. ESA 2005, 71-82. Web SearchBibTeXDownload
273Approximately Dominating Representatives. Vladlen Koltun, Christos H. Papadimitriou. ICDT 2005, 204-214. Web SearchBibTeXDownload
272The complexity of low-distortion embeddings between point sets. Christos H. Papadimitriou, Shmuel Safra. SODA 2005, 112-118. Web SearchBibTeXDownload
271Computing equilibria in multi-player games. Christos H. Papadimitriou, Tim Roughgarden. SODA 2005, 82-91. Web SearchBibTeXDownload
270Computing correlated equilibria in multi-player games. Christos H. Papadimitriou, Tim Roughgarden. STOC 2005, 49-56. Web SearchBibTeXDownload
269On a conjecture related to geometric routing. Christos H. Papadimitriou, David Ratajczak. Theor. Comput. Sci. (344): 3-14 (2005). Web SearchBibTeXDownload
268... The Interaction Between Algorithms and Game Theory. Christos H. Papadimitriou. WEA 2005, 1-3. Web SearchBibTeXDownload
267Experiments with an Economic Model of the Worldwide Web. Georgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri. WINE 2005, 46-54. Web SearchBibTeXDownload
266Recent Developments in Equilibria Algorithms. Christos H. Papadimitriou. WINE 2005, 1-2. Web SearchBibTeXDownload
265An economic model of the worldwide web. Georgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri. WWW (Special interest tracks and posters) 2005, 934-935. Web SearchBibTeXDownload
2004
264On a Conjecture Related to Geometric Routing. Christos H. Papadimitriou, David Ratajczak. ALGOSENSORS 2004, 9-17. Web SearchBibTeXDownload
263Networks and Games. Christos H. Papadimitriou. HiPC 2004, 7. Web SearchBibTeXDownload
262Segmentation problems. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. J. ACM (51): 263-280 (2004). Web SearchBibTeXDownload
261Global Synchronization in Sensornets. Jeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker. LATIN 2004, 609-624. Web SearchBibTeXDownload
260Selfish caching in distributed systems: a game-theoretic analysis. Byung-Gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos H. Papadimitriou, John Kubiatowicz. PODC 2004, 21-30. Web SearchBibTeXDownload
259The complexity of pure Nash equilibria. Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar. STOC 2004, 604-612. Web SearchBibTeXDownload
2003
258A simple algorithm for finding frequent elements in streams and bags. Richard M. Karp, Scott Shenker, Christos H. Papadimitriou. ACM Trans. Database Syst. (28): 51-55 (2003). Web SearchBibTeXDownload
257Games and Networks. Christos H. Papadimitriou. FCT 2003, 157. Web SearchBibTeXDownload
256On Certain Connectivity Properties of the Internet Topology. Milena Mihail, Christos H. Papadimitriou, Amin Saberi. FOCS 2003, 28-35. Web SearchBibTeXDownload
255On the complexity of single-rule datalog queries. Georg Gottlob, Christos H. Papadimitriou. Inf. Comput. (183): 104-122 (2003). Web SearchBibTeXDownload
254An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents. Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos. Internet Mathematics (1) (2003). Web SearchBibTeX
253Mythematics: storytelling in the teaching of computer science and mathematics. Christos H. Papadimitriou. ITiCSE 2003, 1. Web SearchBibTeXDownload
252On the complexity of price equilibria. Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra. J. Comput. Syst. Sci. (67): 311-324 (2003). Web SearchBibTeXDownload
251Auditing Boolean attributes. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. J. Comput. Syst. Sci. (66): 244-253 (2003). Cited by 91Web SearchBibTeXDownload
250Geographic routing without location information. Ananth Rao, Christos H. Papadimitriou, Scott Shenker, Ion Stoica. MOBICOM 2003, 96-108. Web SearchBibTeXDownload
249The New Problems. Christos H. Papadimitriou. PCK50 2003, 10. Web SearchBibTeX
248On a network creation game. Alex Fabrikant, Ankur Luthra, Elitza N. Maneva, Christos H. Papadimitriou, Scott Shenker. PODC 2003, 347-351. Web SearchBibTeXDownload
247MythematiCS: in praise of storytelling in the teaching of computer science and math. Christos H. Papadimitriou. SIGCSE Bulletin (35): 7-9 (2003). Web SearchBibTeXDownload
246An approximate truthful mechanism for combinatorial auctions with single parameter agents. Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos. SODA 2003, 205-214. Web SearchBibTeXDownload
2002
245Learning the Internet. Christos H. Papadimitriou. COLT 2002, 396. Web SearchBibTeXDownload
244Market Equilibrium via a Primal-Dual-Type Algorithm. Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani. FOCS 2002, 389-395. Web SearchBibTeXDownload
243Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou. ICALP 2002, 110-122. Web SearchBibTeXDownload
242Map graphs. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. J. ACM (49): 127-138 (2002). Web SearchBibTeXDownload
241On a model of indexability and its bounds for range queries. Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, Vasilis Samoladas. J. ACM (49): 35-55 (2002). Cited by 16Web SearchBibTeXDownload
240Special Issue on PODS 1999 - Guest Editors' Foreword. Yannis E. Ioannidis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (64): 441-442 (2002). Web SearchBibTeXDownload
239The Internet, the Web, and Algorithms. Christos H. Papadimitriou. LATIN 2002, 2. Web SearchBibTeXDownload
238A BGP-based mechanism for lowest-cost routing. Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker. PODC 2002, 173-182. Web SearchBibTeXDownload
237On the Eigenvalue Power Law. Milena Mihail, Christos H. Papadimitriou. RANDOM 2002, 254-262. Web SearchBibTeXDownload
236Understanding the Internet. Christos H. Papadimitriou. SETN 2002, 1-2. Web SearchBibTeXDownload
235Selfish behavior and stability of the internet: a game-theoretic analysis of TCP. Aditya Akella, Srinivasan Seshan, Richard M. Karp, Scott Shenker, Christos H. Papadimitriou. SIGCOMM 2002, 117-130. Web SearchBibTeXDownload
234On the complexity of equilibria. Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra. STOC 2002, 67-71. Web SearchBibTeXDownload
233The Joy of Theory. Christos H. Papadimitriou. STOC 2002, 116. Web SearchBibTeXDownload
232A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search. Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning. Theor. Comput. Sci. (289): 69-83 (2002). Cited by 143Web SearchBibTeXDownload
2001
231Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. Christos H. Papadimitriou. FOCS 2001, 4-8. Web SearchBibTeXDownload
230Algorithmic problems related to the Internet. Christos H. Papadimitriou. HERCMA 2001, 92. Web SearchBibTeX
229Algorithms, Games, and the Internet. Christos H. Papadimitriou. ICALP 2001, 1-3. Web SearchBibTeXDownload
228On Approximating a Scheduling Problem. Pierluigi Crescenzi, Xiaotie Deng, Christos H. Papadimitriou. J. Comb. Optim. (5): 287-297 (2001). Web SearchBibTeXDownload
227Sharing the Cost of Multicast Transmissions. Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker. J. Comput. Syst. Sci. (63): 21-41 (2001). Web SearchBibTeXDownload
226Multiobjective Query Optimization. Christos H. Papadimitriou, Mihalis Yannakakis. PODS 2001. Web SearchBibTeXDownload
225Game theory, algorithms, and the Internet. Christos H. Papadimitriou. SODA 2001, 391. Web SearchBibTeXDownload
224Algorithms, games, and the internet. Christos H. Papadimitriou. STOC 2001, 749-753. Web SearchBibTeXDownload
223Deciding stability and mortality of piecewise affine dynamical systems. Vincent D. Blondel, Olivier Bournez, Pascal Koiran, Christos H. Papadimitriou, John N. Tsitsiklis. Theor. Comput. Sci. (255): 687-696 (2001). Web SearchBibTeXDownload
2000
222Theoretical Problems Related to the Internet. Christos H. Papadimitriou. COCOON 2000, 1-2. Web SearchBibTeXDownload
221On the Approximability of Trade-offs and Optimal Access of Web Sources. Christos H. Papadimitriou, Mihalis Yannakakis. FOCS 2000, 86-92. Web SearchBibTeXDownload
220Optimization Problems in Congestion Control. Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker. FOCS 2000, 66-74. Web SearchBibTeXDownload
219Latent Semantic Indexing: A Probabilistic Analysis. Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala. J. Comput. Syst. Sci. (61): 217-235 (2000). Cited by 463Web SearchBibTeXDownload
218Distance-Based Reconstruction of Tree Models for Oncogenesis. Richard Desper, Feng Jiang, Olli-P. Kallioniemi, Holger Moch, Christos H. Papadimitriou, Alejandro A. Schäffer. Journal of Computational Biology (7): 789-803 (2000). Web SearchBibTeX
217On certain rigorous approaches to data mining (invited talk, abstract only). Christos H. Papadimitriou. KDD 2000, 2. Web SearchBibTeXDownload
216Auditing Boolean Attributes. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. PODS 2000, 86-91. Web SearchBibTeX
215Beyond Competitive Analysis. Elias Koutsoupias, Christos H. Papadimitriou. SIAM J. Comput. (30): 300-317 (2000). Web SearchBibTeXDownload
214On the Difficulty of Designing Good Classifiers. Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou. SIAM J. Comput. (30): 318-323 (2000). Web SearchBibTeXDownload
213Reminiscences on Influential Papers. Kenneth A. Ross, Amr El Abbadi, Sophie Cluet, Kaladhar Voruganti, Guy M. Lohman, Moshe Y. Vardi, Gultekin Özsoyoglu, Gerhard Weikum, Philip S. Yu, Timos K. Sellis, Patrick Valduriez. SIGMOD Record (29): 52-65 (2000). Web SearchBibTeXDownload
212Sharing the cost of muliticast transmissions (preliminary version). Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker. STOC 2000, 218-227. Web SearchBibTeXDownload
211On the approximability of the traveling salesman problem (extended abstract). Christos H. Papadimitriou, Santosh Vempala. STOC 2000, 126-133. Web SearchBibTeXDownload
1999
210Map Graphs. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. CoRR (cs.DM/9910013) (1999). Web SearchBibTeXDownload
209Software Synthesis of Variable-length Code Decoder Using a Mixture of Programmed Logic and Table Lookups. Gene Cheung, Steven McCanne, Christos H. Papadimitriou. Data Compression Conference 1999, 121-130. Web SearchBibTeXDownload
208Algorithmic Aspects of Protein Structure Similarity. Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou. FOCS 1999, 512-522. Web SearchBibTeXDownload
207Novel Computational Approaches to Information Retrieval and Data Mining (Abstract). Christos H. Papadimitriou. ICDT 1999, 31. Web SearchBibTeXDownload
206Topological Queries in Spatial Databases. Christos H. Papadimitriou, Dan Suciu, Victor Vianu. J. Comput. Syst. Sci. (58): 29-53 (1999). Cited by 97Web SearchBibTeXDownload
205On the Complexity of Database Queries. Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (58): 407-427 (1999). Web SearchBibTeXDownload
204On the Floyd-Warshall Algorithm for Logic Programs. Christos H. Papadimitriou, Martha Sideri. J. Log. Program. (41): 129-137 (1999). Web SearchBibTeXDownload
203Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data. Richard Desper, Feng Jiang, Olli-P. Kallioniemi, Holger Moch, Christos H. Papadimitriou, Alejandro A. Schäffer. Journal of Computational Biology (6): 37-52 (1999). Web SearchBibTeX
202On the Complexity of Single-Rule Datalog Queries. Georg Gottlob, Christos H. Papadimitriou. LPAR 1999, 201-222. Web SearchBibTeXDownload
201Topological Queries. Bart Kuijpers, Victor Vianu. SSD 1999, 3-4. Cited by 4Web SearchBibTeXDownload
200Worst-case Equilibria. Elias Koutsoupias, Christos H. Papadimitriou. STACS 1999, 404-413. Web SearchBibTeXDownload
1998
199Algorithmic Approaches to Information Retrieval and Data Mining (Abstract). Christos H. Papadimitriou. COCOON 1998, 1. Web SearchBibTeXDownload
198Incremental Recompilation of Knowledge. Goran Gogic, Christos H. Papadimitriou, Martha Sideri. CoRR (cs.AI/9801101): 23-37 (1998). Web SearchBibTeXDownload
197A Microeconomic View of Data Mining. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. Data Min. Knowl. Discov. (2): 311-324 (1998). Cited by 119Web SearchBibTeXDownload
196Reflective Relational Machines. Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu. Inf. Comput. (143): 110-136 (1998). Cited by 13Web SearchBibTeXDownload
195How to Learn an Unknown Environment I: The Rectilinear Case. Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou. J. ACM (45): 215-245 (1998). Web SearchBibTeXDownload
194On the Complexity of Protein Folding. Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis. Journal of Computational Biology (5): 423-466 (1998). Web SearchBibTeX
193Latent Semantic Indexing: A Probabilistic Analysis. Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala. PODS 1998, 159-168. Cited by 463Web SearchBibTeX
192On the complexity of protein folding (abstract). Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis. RECOMB 1998, 61-62. Web SearchBibTeXDownload
191Elements of the Theory of Computation. Harry R. Lewis, Christos H. Papadimitriou. SIGACT News (29): 62-78 (1998). Web SearchBibTeXDownload
190Segmentation Problems. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. STOC 1998, 473-482. Cited by 103Web SearchBibTeXDownload
189Planar Map Graphs. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. STOC 1998, 514-523. Web SearchBibTeXDownload
188On the Complexity of Protein Folding (Extended Abstract). Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis. STOC 1998, 597-603. Web SearchBibTeXDownload
1997
187On Kernels, Defaults and Even Graphs. Yannis Dimopoulos, Vangelis Magirou, Christos H. Papadimitriou. Ann. Math. Artif. Intell. (20): 1-12 (1997). Web SearchBibTeXDownload
186Planar Topological Queries. Christos H. Papadimitriou. CDB 1997, 1-6. Web SearchBibTeXDownload
185NP-Completeness: A Retrospective. Christos H. Papadimitriou. ICALP 1997, 2-6. Web SearchBibTeXDownload
184Decision-Making by Hierarchies of Discordant Agents. Xiaotie Deng, Christos H. Papadimitriou. ISAAC 1997, 183-192. Web SearchBibTeXDownload
183Tie-Breaking Semantics and Structural Totality. Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (54): 48-60 (1997). Web SearchBibTeXDownload
182On the Analysis of Indexing Schemes. Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou. PODS 1997, 249-256. Cited by 121Web SearchBibTeX
181On the Complexity of Database Queries. Christos H. Papadimitriou, Mihalis Yannakakis. PODS 1997, 12-19. Web SearchBibTeX
180Emerging opportunities for theoretical computer science. Alfred V. Aho, David S. Johnson, Richard M. Karp, S. Rao Kosaraju, Catherine C. McGeoch, Christos H. Papadimitriou, Pavel A. Pevzner. SIGACT News (28): 65-74 (1997). Web SearchBibTeXDownload
179Panarity, Revisited (Extended Abstract). Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. WADS 1997, 472-473. Web SearchBibTeXDownload
1996
178Competitive Distributed Decision-Making. Xiaotie Deng, Christos H. Papadimitriou. Algorithmica (16): 133-150 (1996). Web SearchBibTeXDownload
177On the Difficulty of Designing Good Classifiers. Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou. COCOON 1996, 273-279. Web SearchBibTeXDownload
176Computational Aspacts of Organization Theory (Extended Abstract). Christos H. Papadimitriou. ESA 1996, 559-564. Web SearchBibTeXDownload
175Searching a Fixed Graph. Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis. ICALP 1996, 280-289. Web SearchBibTeXDownload
174The Complexity of Knowledge Representation. Christos H. Papadimitriou. IEEE Conference on Computational Complexity 1996, 244-248. Web SearchBibTeXDownload
173The 2-Evader Problem. Elias Koutsoupias, Christos H. Papadimitriou. Inf. Process. Lett. (57): 249-252 (1996). Web SearchBibTeXDownload
172On Limited Nondeterminism and the Complexity of the V-C Dimension. Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (53): 161-170 (1996). Web SearchBibTeXDownload
171The Bisection Width of Grid Graphs. Christos H. Papadimitriou, Martha Sideri. Mathematical Systems Theory (29): 97-110 (1996). Web SearchBibTeXDownload
170In Memoriam: Paris C. Kanellakis. Pascal Van Hentenryck, Gabriel M. Kuper, Christos H. Papadimitriou, Moshe Y. Vardi. PODS 1996, 79. Cited by 2Web SearchBibTeX
169Topological Queries in Spatial Databases. Christos H. Papadimitriou, Dan Suciu, Victor Vianu. PODS 1996, 81-92. Cited by 97Web SearchBibTeX
168The future of computational complexity theory: part I. Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser. SIGACT News (27): 6-12 (1996). Web SearchBibTeXDownload
1995
167Multimedia Information Caching for Personalized Video-on-Demand. Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan, Srihari Sampath Kumar. Computer Communications (18): 204-216 (1995). Web SearchBibTeX
166An Approximation Scheme for Planar Graph TSP. Michelangelo Grigni, Elias Koutsoupias, Christos H. Papadimitriou. FOCS 1995, 640-645. Web SearchBibTeXDownload
165Topological Inference. Michelangelo Grigni, Dimitris Papadias, Christos H. Papadimitriou. IJCAI (1) 1995, 901-907. Cited by 161Web SearchBibTeX
164The Comparative Linguistics of Knowledge Representation. Goran Gogic, Henry A. Kautz, Christos H. Papadimitriou, Bart Selman. IJCAI (1) 1995, 862-869. Web SearchBibTeX
163Optimal Information Delivery. Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan. ISAAC 1995, 181-187. Web SearchBibTeXDownload
162On the k-Server Conjecture. Elias Koutsoupias, Christos H. Papadimitriou. J. ACM (42): 971-983 (1995). Web SearchBibTeXDownload
161Database Metatheory: Asking the Big Queries. Christos H. Papadimitriou. PODS 1995, 1-10. Web SearchBibTeXDownload
160Database metatheory: asking the big queries. Christos H. Papadimitriou. SIGACT News (26): 13-30 (1995). Web SearchBibTeXDownload
159Reversible Simulation of Space-Bounded Computations. Pierluigi Crescenzi, Christos H. Papadimitriou. Theor. Comput. Sci. (143): 159-165 (1995). Web SearchBibTeXDownload
1994
158Incremental Recompilation of Knowledge. Goran Gogic, Christos H. Papadimitriou, Martha Sideri. AAAI 1994, 922-927. Web SearchBibTeX
157Designing Secure Communication Protocols from Trust Specification. Christos H. Papadimitriou, P. Venkat Rangan, Martha Sideri. Algorithmica (11): 485-499 (1994). Web SearchBibTeXDownload
156Default Theories that Always Have Extensions. Christos H. Papadimitriou, Martha Sideri. Artif. Intell. (69): 347-357 (1994). Web SearchBibTeXDownload
155On the Random Walk Method for Protocol Testing. Milena Mihail, Christos H. Papadimitriou. CAV 1994, 132-141. Web SearchBibTeXDownload
154Motion Planning on a Graph (Extended Abstract). Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki. FOCS 1994, 511-520. Web SearchBibTeXDownload
153Beyond Competitive Analysis. Elias Koutsoupias, Christos H. Papadimitriou. FOCS 1994, 394-400. Web SearchBibTeXDownload
152Information Caching for Delivery of Personalized Video Programs on Home Entertainment Channels. Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan. ICMCS 1994, 214-223. Web SearchBibTeX
151On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. Christos H. Papadimitriou. J. Comput. Syst. Sci. (48): 498-532 (1994). Web SearchBibTeXDownload
150The Power of Reflective Relational Machines. Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu. LICS 1994, 230-240. Cited by 21Web SearchBibTeXDownload
149The Complexity of Multiterminal Cuts. Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis. SIAM J. Comput. (23): 864-894 (1994). Web SearchBibTeXDownload
148On complexity as bounded rationality (extended abstract). Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1994, 726-733. Web SearchBibTeXDownload
147The Complexity of Optimal Queueing Network Control. Christos H. Papadimitriou, John N. Tsitsiklis. Structure in Complexity Theory Conference 1994, 318-322. Web SearchBibTeX
1993
146Computing the Throughput of a Network with Dedicated Lines. Christos H. Papadimitriou, Paolo Serafini, Mihalis Yannakakis. Discrete Applied Mathematics (42): 271-278 (1993). Web SearchBibTeXDownload
145On Horn Envelopes and Hypergraph Transversals. Dimitris J. Kavvadias, Christos H. Papadimitriou, Martha Sideri. ISAAC 1993, 399-405. Web SearchBibTeXDownload
144The Parallel Complexity of Simple Logic Programs. Foto N. Afrati, Christos H. Papadimitriou. J. ACM (40): 891-916 (1993). Cited by 13Web SearchBibTeXDownload
143Linear programming without the matrix. Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1993, 121-129. Web SearchBibTeXDownload
142On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. Structure in Complexity Theory Conference 1993, 12-18. Web SearchBibTeX
1992
141On Finding Extensions of Default Theories. Christos H. Papadimitriou, Martha Sideri. ICDT 1992, 276-281. Web SearchBibTeXDownload
140Competitive Distributed Decision-Making. Xiaotie Deng, Christos H. Papadimitriou. IFIP Congress (1) 1992, 350-356. Web SearchBibTeX
139On the Optimal Bisection of a Polygon. Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri. INFORMS Journal on Computing (4): 435-438 (1992). Web SearchBibTeXDownload
138On the Greedy Algorithm for Satisfiability. Elias Koutsoupias, Christos H. Papadimitriou. Inf. Process. Lett. (43): 53-55 (1992). Web SearchBibTeXDownload
137Tie-Breaking Semantics and Structural Totality. Christos H. Papadimitriou, Mihalis Yannakakis. PODS 1992, 16-22. Web SearchBibTeX
136The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem. Christos H. Papadimitriou. SIAM J. Comput. (21): 450-465 (1992). Web SearchBibTeXDownload
135The Complexity of Multiway Cuts (Extended Abstract). Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis. STOC 1992, 241-251. Web SearchBibTeXDownload
1991
134On Selecting a Satisfying Truth Assignment (Extended Abstract). Christos H. Papadimitriou. FOCS 1991, 163-169. Web SearchBibTeXDownload
133How to Learn an Unknown Environment (Extended Abstract). Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou. FOCS 1991, 298-303. Web SearchBibTeXDownload
132Designing Secure Communication Protocols from Trust Specifications. Christos H. Papadimitriou, P. Venkat Rangan, Martha Sideri. FSTTCS 1991, 360-368. Web SearchBibTeXDownload
131Decision-Making with Incomplete Information. Christos H. Papadimitriou. ISA 1991, 1. Web SearchBibTeXDownload
130Modularity of Cycles and Paths in Graphs. Esther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis. J. ACM (38): 255-274 (1991). Web SearchBibTeXDownload
129The Weighted Region Problem: Finding Shortest Paths Through a Weighted Planar Subdivision. Joseph S. B. Mitchell, Christos H. Papadimitriou. J. ACM (38): 18-73 (1991). Web SearchBibTeXDownload
128Why not Negation by Fixpoint?. Phokion G. Kolaitis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (43): 125-144 (1991). Web SearchBibTeXDownload
127Optimization, Approximation, and Complexity Classes. Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (43): 425-440 (1991). Web SearchBibTeXDownload
126On the Value of Information in Distributed Decision-Making (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. PODC 1991, 61-64. Web SearchBibTeX
125Optimal Coteries. Christos H. Papadimitriou, Martha Sideri. PODC 1991, 75-80. Web SearchBibTeX
124Shortest Paths Without a Map. Christos H. Papadimitriou, Mihalis Yannakakis. Theor. Comput. Sci. (84): 127-150 (1991). Web SearchBibTeXDownload
123On Total Functions, Existence Theorems and Computational Complexity. Nimrod Megiddo, Christos H. Papadimitriou. Theor. Comput. Sci. (81): 317-324 (1991). Web SearchBibTeXDownload
1990
122A Linear Programming Approach to Reasoning about Probabilities. Dimitris J. Kavvadias, Christos H. Papadimitriou. Ann. Math. Artif. Intell. (1): 189-205 (1990). Web SearchBibTeXDownload
121On recognizing integer polyhedra. Christos H. Papadimitriou, Mihalis Yannakakis. Combinatorica (10): 107-109 (1990). Web SearchBibTeXDownload
120On the Predictability of Coupled Automata: An Allegory about Chaos. Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis. FOCS 1990, 788-793. Web SearchBibTeXDownload
119Exploring an Unknown Graph (Extended Abstract). Xiaotie Deng, Christos H. Papadimitriou. FOCS 1990, 355-361. Web SearchBibTeXDownload
118On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract). Christos H. Papadimitriou. FOCS 1990, 794-801. Web SearchBibTeXDownload
117The Geometry of Grasping. Xanthippi Markenscoff, Luqun Ni, Christos H. Papadimitriou. I. J. Robotic Res. (9): 61-74 (1990). Web SearchBibTeX
116The Optimum Execution Order of Queries in Linear Storage. John G. Kollias, Yannis Manolopoulos, Christos H. Papadimitriou. Inf. Process. Lett. (36): 141-145 (1990). Cited by 7Web SearchBibTeXDownload
115Some Computational Aspects of Circumscription. Phokion G. Kolaitis, Christos H. Papadimitriou. J. ACM (37): 1-14 (1990). Web SearchBibTeXDownload
114Towards an Architecture-Independent Analysis of Parallel Algorithms. Christos H. Papadimitriou, Mihalis Yannakakis. SIAM J. Comput. (19): 322-328 (1990). Web SearchBibTeXDownload
113The Bisection Width of Grid Graphs. Christos H. Papadimitriou, Martha Sideri. SODA 1990, 405-410. Web SearchBibTeXDownload
112On the Complexity of Local Search (Extended Abstract). Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis. STOC 1990, 438-445. Web SearchBibTeXDownload
111On the Optimal Bisection of a Polygon (Extended Abstract). Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri. Symposium on Computational Geometry 1990, 198-202. Web SearchBibTeXDownload
1989
110Shortest Paths Without a Map. Christos H. Papadimitriou, Mihalis Yannakakis. ICALP 1989, 610-620. Web SearchBibTeXDownload
109Optimum Grip of a Polygon. Xanthippi Markenscoff, Christos H. Papadimitriou. I. J. Robotic Res. (8): 17-29 (1989). Web SearchBibTeX
108Corrigendum: The Complexity of Cubical Graphs. Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou. Inf. Comput. (82): 350-353 (1989). Web SearchBibTeXDownload
107Finding Feasible Paths for a Two-Point Body. Ellen B. Feinberg, Christos H. Papadimitriou. J. Algorithms (10): 109-119 (1989). Web SearchBibTeXDownload
106Exponential lower bounds for finding Brouwer fix points. Michael D. Hirsch, Christos H. Papadimitriou, Stephen A. Vavasis. J. Complexity (5): 379-416 (1989). Web SearchBibTeXDownload
105On the Convergence of Query Evaluation. Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman. J. Comput. Syst. Sci. (38): 341-359 (1989). Cited by 10Web SearchBibTeXDownload
1988
104Some Computational Aspects of Circumscription. Phokion G. Kolaitis, Christos H. Papadimitriou. AAAI 1988, 455-469. Web SearchBibTeX
103The Synthesis of Communication Protocols. Foto N. Afrati, Christos H. Papadimitriou, Georgios I. Papadimitriou. Algorithmica (3): 451-472 (1988). Cited by 5Web SearchBibTeXDownload
102Scheduling Dags to Minimize Time and Communication. Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou. AWOC 1988, 134-138. Cited by 11Web SearchBibTeXDownload
101Complexity Characterizations of Attribute Grammar Languages. Sophocles Ephremidis, Christos H. Papadimitriou, Martha Sideri. Inf. Comput. (78): 178-186 (1988). Web SearchBibTeXDownload
100On Generating All Maximal Independent Sets. David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis. Inf. Process. Lett. (27): 119-123 (1988). Web SearchBibTeXDownload
99The complexity of searching a graph. Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou. J. ACM (35): 18-44 (1988). Web SearchBibTeXDownload
98Probabilistic satisfiability. George F. Georgakopoulos, Dimitris J. Kavvadias, Christos H. Papadimitriou. J. Complexity (4): 1-11 (1988). Web SearchBibTeXDownload
97The Complexity of Recognizing Polyhedral Scenes. Lefteris M. Kirousis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (37): 14-38 (1988). Web SearchBibTeXDownload
96How Easy is Local Search?. David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (37): 79-100 (1988). Web SearchBibTeXDownload
95The Complexity of Facets Resolved. Christos H. Papadimitriou, David Wolfe. J. Comput. Syst. Sci. (37): 2-13 (1988). Web SearchBibTeXDownload
94Why Not Negation by Fixpoint?. Phokion G. Kolaitis, Christos H. Papadimitriou. PODS 1988, 231-239. Web SearchBibTeX
93Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1988, 510-513. Web SearchBibTeXDownload
92Optimization, Approximation, and Complexity Classes (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1988, 229-234. Web SearchBibTeXDownload
1987
91Optimal Piecewise Linear Motion of an Object Among Obstacles. Christos H. Papadimitriou, Ellen B. Silverberg. Algorithmica (2): 523-539 (1987). Web SearchBibTeXDownload
90The 1-Steiner Tree Problem. George K. Georgakopoulos, Christos H. Papadimitriou. J. Algorithms (8): 122-130 (1987). Web SearchBibTeXDownload
89The Parallel Complexity of Simple Chain Queries. Foto N. Afrati, Christos H. Papadimitriou. PODS 1987, 210-213. Cited by 40Web SearchBibTeX
88The Complexity of Reliable Concurrency Control. Christos H. Papadimitriou, Mihalis Yannakakis. SIAM J. Comput. (16): 538-553 (1987). Web SearchBibTeXDownload
87A Communication-Time Tradeoff. Christos H. Papadimitriou, Jeffrey D. Ullman. SIAM J. Comput. (16): 639-646 (1987). Cited by 85Web SearchBibTeXDownload
86The Discrete Geodesic Problem. Joseph S. B. Mitchell, David M. Mount, Christos H. Papadimitriou. SIAM J. Comput. (16): 647-668 (1987). Web SearchBibTeXDownload
85On Stochastic Scheduling with In-Tree Precedence Constraints. Christos H. Papadimitriou, John N. Tsitsiklis. SIAM J. Comput. (16): 1-6 (1987). Web SearchBibTeXDownload
84The Weighted Region Problem. Joseph S. B. Mitchell, Christos H. Papadimitriou. Symposium on Computational Geometry 1987, 30-38. Web SearchBibTeXDownload
1986
83Shortest-Path Motion. Christos H. Papadimitriou. FSTTCS 1986, 144-153. Web SearchBibTeXDownload
82A Note on Succinct Representations of Graphs. Christos H. Papadimitriou, Mihalis Yannakakis. Information and Control (71): 181-185 (1986). Web SearchBibTeXDownload
81The Complexity of the Travelling Repairman Problem. Foto N. Afrati, Stavros S. Cosmadakis, Christos H. Papadimitriou, George Papageorgiou, Nadia Papakostantinou. ITA (20): 79-87 (1986). Cited by 2Web SearchBibTeX
80The performance of a precedence-based queuing discipline. John N. Tsitsiklis, Christos H. Papadimitriou, Pierre A. Humblet. J. ACM (33): 593-602 (1986). Web SearchBibTeXDownload
79On the Complexity of Circulations. Esther M. Arkin, Christos H. Papadimitriou. J. Algorithms (7): 134-145 (1986). Web SearchBibTeXDownload
78Algorithmic Aspects of Multiversion Concurrency Control. Thanasis Hadzilacos, Christos H. Papadimitriou. J. Comput. Syst. Sci. (33): 297-310 (1986). Web SearchBibTeXDownload
77The Synthesis of Communication Protocols. Foto N. Afrati, Christos H. Papadimitriou, Georgios I. Papadimitriou. PODC 1986, 263-271. Cited by 5Web SearchBibTeX
76Convergence of Sideways Query Evaluation. Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman. PODS 1986, 24-30. Cited by 12Web SearchBibTeX
75Searching and Pebbling. Lefteris M. Kirousis, Christos H. Papadimitriou. Theor. Comput. Sci. (47): 205-218 (1986). Web SearchBibTeXDownload
1985
74A note the expressive power of Prolog. Christos H. Papadimitriou. Bulletin of the EATCS (26): 21-22 (1985). Web SearchBibTeX
73Interval graphs and seatching. Lefteris M. Kirousis, Christos H. Papadimitriou. Discrete Mathematics (55): 181-184 (1985). Web SearchBibTeXDownload
72The Complexity of Facets Resolved. Christos H. Papadimitriou, David Wolfe. FOCS 1985, 74-78. Web SearchBibTeXDownload
71The Complexity of Recognizing Polyhedral Scenes (Extended Abstract). Lefteris M. Kirousis, Christos H. Papadimitriou. FOCS 1985, 175-185. Web SearchBibTeXDownload
70How Easy Is Local Search? (Extended Abstract). David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis. FOCS 1985, 39-42. Web SearchBibTeXDownload
69The Complexity of Cubical Graphs. Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou. Information and Control (66): 53-60 (1985). Cited by 13Web SearchBibTeXDownload
68An Algorithm for Shortest-Path Motion in Three Dimensions. Christos H. Papadimitriou. Inf. Process. Lett. (20): 259-263 (1985). Web SearchBibTeXDownload
67Correction to ``A Theorem in Database Concurrency Control''. Christos H. Papadimitriou. J. ACM (32): 750 (1985). Web SearchBibTeX
66Games Against Nature. Christos H. Papadimitriou. J. Comput. Syst. Sci. (31): 288-301 (1985). Web SearchBibTeXDownload
65The Complexity of Reliable Concurrency Control. Christos H. Papadimitriou, Mihalis Yannakakis. PODS 1985, 230-234. Web SearchBibTeX
64Algorithmic Aspects of Multiversion Concurrency Control. Thanasis Hadzilacos, Christos H. Papadimitriou. PODS 1985, 96-104. Web SearchBibTeX
63The Complexity of Distributed Concurrency Control. Paris C. Kanellakis, Christos H. Papadimitriou. SIAM J. Comput. (14): 52-74 (1985). Web SearchBibTeXDownload
1984
62On Concurrency Control by Multiple Versions. Christos H. Papadimitriou, Paris C. Kanellakis. ACM Trans. Database Syst. (9): 89-99 (1984). Web SearchBibTeXDownload
61A Communication-Time Tradeoff. Christos H. Papadimitriou, Jeffrey D. Ullman. FOCS 1984, 84-88. Cited by 85Web SearchBibTeXDownload
60The Complexity of Cubical Graphs (Extended Abstract). Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou. ICALP 1984, 51-57. Web SearchBibTeXDownload
59Updates of Relational Views. Stavros S. Cosmadakis, Christos H. Papadimitriou. J. ACM (31): 742-760 (1984). Web SearchBibTeXDownload
58On the complexity of unique solutions. Christos H. Papadimitriou. J. ACM (31): 392-400 (1984). Web SearchBibTeXDownload
57On Two Geometric Problems Related to the Traveling Salesman Problem. Christos H. Papadimitriou, Umesh V. Vazirani. J. Algorithms (5): 231-246 (1984). Web SearchBibTeXDownload
56Communication Complexity. Dömötör Pálvölgyi, Michael Sipser. J. Comput. Syst. Sci. (28): 260-269 (1984). Web SearchBibTeXDownload
55Inclusion Dependencies and Their Interaction with Functional Dependencies. Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou. J. Comput. Syst. Sci. (28): 29-59 (1984). Web SearchBibTeXDownload
54The Complexity of Facets (and Some Facets of Complexity). Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (28): 244-259 (1984). Web SearchBibTeXDownload
53Is Distributed Locking Harder?. Paris C. Kanellakis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (28): 103-120 (1984). Web SearchBibTeXDownload
52The Traveling Salesman Problem with Many Visits to Few Cities. Stavros S. Cosmadakis, Christos H. Papadimitriou. SIAM J. Comput. (13): 99-108 (1984). Web SearchBibTeXDownload
1983
51An Optimality Theory of Concurrency Control for Databases. H. T. Kung, Christos H. Papadimitriou. Acta Inf. (19): 1-11 (1983). Web SearchBibTeXDownload
50Topological Bandwidth. Fillia Makedon, Christos H. Papadimitriou, Ivan Hal Sudborough. CAAP 1983, 317-331. Web SearchBibTeXDownload
49Games Against Nature (Extended Abstract). Christos H. Papadimitriou. FOCS 1983, 446-450. Web SearchBibTeXDownload
48Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract). Mihalis Yannakakis, Paris C. Kanellakis, Stavros S. Cosmadakis, Christos H. Papadimitriou. ICALP 1983, 712-722. Web SearchBibTeXDownload
47Updates of Relational Views. Stavros S. Cosmadakis, Christos H. Papadimitriou. PODS 1983, 317-331. Web SearchBibTeX
46Concurrency Control by Locking. Christos H. Papadimitriou. SIAM J. Comput. (12): 215-226 (1983). Web SearchBibTeXDownload
45Theory of concurrency control. Christos H. Papadimitriou. Theoretical Computer Science 1983, 35-47. Web SearchBibTeXDownload
44Two remarks on the power of counting. Christos H. Papadimitriou, Stathis Zachos. Theoretical Computer Science 1983, 269-276. Web SearchBibTeXDownload
1982
43On the Complexity of Unique Solutions. Christos H. Papadimitriou. FOCS 1982, 14-20. Web SearchBibTeXDownload
42On the Complexity of Designing Distributed Protocols. Christos H. Papadimitriou, John N. Tsitsiklis. Information and Control (53): 211-218 (1982). Web SearchBibTeXDownload
41A theorem in database concurrency control. Christos H. Papadimitriou. J. ACM (29): 998-1006 (1982). Web SearchBibTeXDownload
40The complexity of restricted spanning tree problems. Christos H. Papadimitriou, Mihalis Yannakakis. J. ACM (29): 285-309 (1982). Web SearchBibTeXDownload
39Algebraic Dependencies. Mihalis Yannakakis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (25): 2-41 (1982). Web SearchBibTeXDownload
38Inclusion Dependencies and Their Interaction with Functional Dependencies. Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou. PODS 1982, 171-176. Web SearchBibTeX
37On Concurrency Control by Multiple Versions. Christos H. Papadimitriou, Paris C. Kanellakis. PODS 1982, 76-82. Web SearchBibTeX
36Is Distributed Locking Harder?. Paris C. Kanellakis, Christos H. Papadimitriou. PODS 1982, 98-107. Web SearchBibTeX
35On Linear Characterizations of Combinatorial Optimization Problems. Richard M. Karp, Christos H. Papadimitriou. SIAM J. Comput. (11): 620-632 (1982). Web SearchBibTeXDownload
34Hamilton Paths in Grid Graphs. Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter. SIAM J. Comput. (11): 676-686 (1982). Web SearchBibTeXDownload
33Communication Complexity. Dömötör Pálvölgyi, Michael Sipser. STOC 1982, 196-200. Web SearchBibTeXDownload
32The Complexity of Facets (and Some Facets of Complexity). Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1982, 255-260. Web SearchBibTeXDownload
31Symmetric Space-Bounded Computation. Harry R. Lewis, Christos H. Papadimitriou. Theor. Comput. Sci. (19): 161-187 (1982). Web SearchBibTeXDownload
1981
30The Complexity of Distributed Concurrency Control. Paris C. Kanellakis, Christos H. Papadimitriou. FOCS 1981, 185-197. Web SearchBibTeXDownload
29The Complexity of Searching a Graph (Preliminary Version). Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou. FOCS 1981, 376-385. Web SearchBibTeXDownload
28Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. FOCS 1981, 358-363. Web SearchBibTeXDownload
27The Complexity of Testing Whether a Graph is a Superconcentrator. Manuel Blum, Richard M. Karp, Oliver Vornberger, Christos H. Papadimitriou, Mihalis Yannakakis. Inf. Process. Lett. (13): 164-167 (1981). Web SearchBibTeXDownload
26The Clique Problem for Planar Graphs. Christos H. Papadimitriou, Mihalis Yannakakis. Inf. Process. Lett. (13): 131-133 (1981). Web SearchBibTeXDownload
25On Minimal Eulerian Graphs. Christos H. Papadimitriou, Mihalis Yannakakis. Inf. Process. Lett. (12): 203-205 (1981). Web SearchBibTeXDownload
24On the complexity of integer programming. Christos H. Papadimitriou. J. ACM (28): 765-768 (1981). Web SearchBibTeXDownload
23A Fast Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems. Witold Lipski Jr., Christos H. Papadimitriou. J. Algorithms (2): 211-226 (1981). Web SearchBibTeXDownload
22Worst-Case and Probabilistic Analysis of a Geometric Location Problem. Christos H. Papadimitriou. SIAM J. Comput. (10): 542-557 (1981). Web SearchBibTeXDownload
21Covering Graphs by Simple Circuits. Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael Rodeh. SIAM J. Comput. (10): 746-750 (1981). Web SearchBibTeXDownload
20On the Power of Locking. Christos H. Papadimitriou. SIGMOD Conference 1981, 148-154. Web SearchBibTeX
1980
19On the Performance of Balanced Hashing Functions When the Keys Are Not Equiprobable. Christos H. Papadimitriou, Philip A. Bernstein. ACM Trans. Program. Lang. Syst. (2): 77-89 (1980). Cited by 1Web SearchBibTeXDownload
18Algebraic Dependencies (Extended Abstract). Mihalis Yannakakis, Christos H. Papadimitriou. FOCS 1980, 328-332. Web SearchBibTeXDownload
17On Linear Characterizations of Combinatorial Optimization Problems. Richard M. Karp, Christos H. Papadimitriou. FOCS 1980, 1-9. Web SearchBibTeXDownload
16A Worst-Case Analysis of Nearest Neighbor Searching by Projection. Christos H. Papadimitriou, Jon Louis Bentley. ICALP 1980, 470-482. Web SearchBibTeXDownload
15Symmetric Space-Bounded Computation (Extended Abstract). Harry R. Lewis, Christos H. Papadimitriou. ICALP 1980, 374-384. Web SearchBibTeXDownload
14Flowshop scheduling with limited temporary storage. Christos H. Papadimitriou, Paris C. Kanellakis. J. ACM (27): 533-549 (1980). Web SearchBibTeXDownload
1979
13Locking Policies: Safety and Freedom from Deadlock. Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung. FOCS 1979, 286-297. Web SearchBibTeXDownload
12The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. ICALP 1979, 460-470. Web SearchBibTeXDownload
11Efficient Search for Rationals. Christos H. Papadimitriou. Inf. Process. Lett. (8): 1-4 (1979). Web SearchBibTeXDownload
10Optimality of the Fast Fourier transform. Christos H. Papadimitriou. J. ACM (26): 95-102 (1979). Web SearchBibTeXDownload
9The serializability of concurrent database updates. Christos H. Papadimitriou. J. ACM (26): 631-653 (1979). Web SearchBibTeXDownload
8Scheduling Interval-Ordered Tasks. Christos H. Papadimitriou, Mihalis Yannakakis. SIAM J. Comput. (8): 405-409 (1979). Web SearchBibTeXDownload
7An Optimality Theory of Concurrency Control for Databases. H. T. Kung, Christos H. Papadimitriou. SIGMOD Conference 1979, 116-126. Web SearchBibTeX
1978
6The Concurrency Control Mechanism of SDD-1: A System for Distributed Databases (The Fully Redundant Case). Philip A. Bernstein, James B. Rothnie Jr., Nathan Goodman, Christos H. Papadimitriou. IEEE Trans. Software Eng. (4): 154-168 (1978). Cited by 87Web SearchBibTeXDownload
1977
5On the Complexity of Local Search for the Traveling Salesman Problem. Christos H. Papadimitriou, Kenneth Steiglitz. SIAM J. Comput. (6): 76-83 (1977). Web SearchBibTeXDownload
4The Euclidean Traveling Salesman Problem is NP-Complete. Christos H. Papadimitriou. Theor. Comput. Sci. (4): 237-244 (1977). Web SearchBibTeXDownload
1976
3The NP-Completeness of the bandwidth minimization problem. Christos H. Papadimitriou. Computing (16): 263-270 (1976). Web SearchBibTeXDownload
2On the complexity of edge traversing. Christos H. Papadimitriou. J. ACM (23): 544-554 (1976). Web SearchBibTeXDownload
1Some Complexity Results for the Traveling Salesman Problem. Christos H. Papadimitriou, Kenneth Steiglitz. STOC 1976, 1-9. Web SearchBibTeXDownload
from DBLP and Google Scholar
References
1. ^ SCHOOL OF COMPUTER SCIENCE, Carnegie Mellon - Retrieved 2011-03-19 - details
2. ^ Events Calendar | CSAIL - Retrieved 2012-01-12 - details
3. ^ Computer Science Colloquium - NYU Computer Science Department - Retrieved 2011-04-23 - details
4. ^ Distinguished Lecture Series - Retrieved 2011-04-16 - details
Developed by the Database Group at the University of Wisconsin and Yahoo! Research