2013
354Learning and Verifying Quantified Boolean Queries by Example. Azza Abouzied, Dana Angluin, Christos H. Papadimitriou, Joseph M. Hellerstein, Avi Silberschatz. CoRR (abs/1304.4303) (2013). Web SearchBibTeXDownload
353Multiplicative updates in coordination games and the theory of evolution. Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani. ITCS 2013, 57-58. Web SearchBibTeXDownload
2012
352Alan and I. Christos H. Papadimitriou. Commun. ACM (55): 42-43 (2012). Web SearchBibTeXDownload
351Efficiency-Revenue Trade-offs in Auctions. Ilias Diakonikolas, Christos H. Papadimitriou, George Pierrakos, Yaron Singer. CoRR (abs/1205.3077) (2012). Web SearchBibTeXDownload
350Multiplicative Updates in Coordination Games and the Theory of Evolution. Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani. CoRR (abs/1208.3160) (2012). Web SearchBibTeXDownload
349Efficiency-Revenue Trade-Offs in Auctions. Ilias Diakonikolas, Christos H. Papadimitriou, George Pierrakos, Yaron Singer. ICALP (2) 2012, 488-499. Web SearchBibTeXDownload
348The New Faces of Combinatorial Optimization. Christos H. Papadimitriou. ISCO 2012, 19-23. Web SearchBibTeXDownload
2011
347Economies with non-convex production and complexity equilibria. Christos H. Papadimitriou, Christopher A. Wilkens. ACM Conference on Electronic Commerce 2011, 137-146. Web SearchBibTeXDownload
346Mechanisms for complement-free procurement. Shahar Dobzinski, Christos H. Papadimitriou, Yaron Singer. ACM Conference on Electronic Commerce 2011, 273-282. Web SearchBibTeXDownload
345On Oblivious PTAS's for Nash Equilibrium. Constantinos Daskalakis, Christos H. Papadimitriou. CoRR (abs/1102.2280) (2011). Web SearchBibTeXDownload
344The 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
343Continuous Local Search. Constantinos Daskalakis, Christos H. Papadimitriou. SODA 2011, 790-804. Web SearchBibTeXDownload
342On optimal single-item auctions. Christos H. Papadimitriou, George Pierrakos. STOC 2011, 119-128. Web SearchBibTeXDownload
341On 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
340Modeling Social Networks through User Background and Behavior. Ilias Foudalis, Kamal Jain, Christos H. Papadimitriou, Martha Sideri. WAW 2011, 85-102. Web SearchBibTeXDownload
339Games, algorithms, and the Internet. Christos H. Papadimitriou. WWW 2011, 5-6. Web SearchBibTeXDownload
2010
338Budget Feasible Mechanisms. Christos H. Papadimitriou, Yaron Singer. CoRR (abs/1002.2334) (2010). Web SearchBibTeXDownload
337The 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
336On Optimal Single-Item Auctions. Christos H. Papadimitriou, George Pierrakos. CoRR (abs/1011.1279) (2010). Web SearchBibTeXDownload
335The myth of the Folk Theorem. Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou. Games and Economic Behavior (70): 34-43 (2010). Web SearchBibTeXDownload
334A New Look at Selfish Routing. Christos H. Papadimitriou, Gregory Valiant. ICS 2010, 178-187. Web SearchBibTeXDownload
333On Learning Algorithms for Nash Equilibria. Constantinos Daskalakis, Rafael Frongillo, Christos H. Papadimitriou, George Pierrakos, Gregory Valiant. SAGT 2010, 114-125. Web SearchBibTeXDownload
332When the Players Are Not Expectation Maximizers. Amos Fiat, Christos H. Papadimitriou. SAGT 2010, 1-14. Web SearchBibTeXDownload
331Inapproximability 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
330The complexity of computing a Nash equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. Commun. ACM (52): 89-97 (2009). Web SearchBibTeXDownload
329Worst-case equilibria. Elias Koutsoupias, Christos H. Papadimitriou. Computer Science Review (3): 65-69 (2009). Web SearchBibTeXDownload
328VC 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
327Comparing Trade-off Based Models of the Internet. Anthony Spatharis, Ilias Foudalis, Martha Sideri, Christos H. Papadimitriou. Fundam. Inform. (92): 363-372 (2009). Web SearchBibTeXDownload
326Congestion games with malicious players. Moshe Babaioff, Robert Kleinberg, Christos H. Papadimitriou. Games and Economic Behavior (67): 22-35 (2009). Web SearchBibTeXDownload
325Algorithmic Game Theory: A Snapshot. Christos H. Papadimitriou. ICALP (1) 2009, 3-11. Web SearchBibTeXDownload
324On a Network Generalization of the Minmax Theorem. Constantinos Daskalakis, Christos H. Papadimitriou. ICALP (2) 2009, 423-434. Web SearchBibTeXDownload
323The ACM PODS Alberto O. Mendelzon test-of-time-award 2009. Catriel Beeri, Phokion G. Kolaitis, Christos H. Papadimitriou. PODS 2009, 43. Web SearchBibTeXDownload
322The 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
321The Complexity of Computing a Nash Equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. SIAM J. Comput. (39): 195-259 (2009). Web SearchBibTeXDownload
320On oblivious PTAS's for nash equilibrium. Constantinos Daskalakis, Christos H. Papadimitriou. STOC 2009, 75-84. Web SearchBibTeXDownload
319A note on approximate Nash equilibria. Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou. Theor. Comput. Sci. (410): 1581-1588 (2009). Web SearchBibTeXDownload
318A Note on Strictly Competitive Games. Ilan Adler, Constantinos Daskalakis, Christos H. Papadimitriou. WINE 2009, 471-474. Web SearchBibTeXDownload
2008
317On the Hardness of Being Truthful. Christos H. Papadimitriou, Michael Schapira, Yaron Singer. FOCS 2008, 250-259. Web SearchBibTeXDownload
316Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. Constantinos Daskalakis, Christos H. Papadimitriou. FOCS (abs/0808.2801): 25-34 (2008). Web SearchBibTeXDownload
315Incentive-Compatible Interdomain Routing with Linear Utilities. Alexander Hall, Evdokia Nikolova, Christos H. Papadimitriou. Internet Mathematics (5): 395-410 (2008). Web SearchBibTeXDownload
314On 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
313Market 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
312Computing correlated equilibria in multi-player games. Christos H. Papadimitriou, Tim Roughgarden. J. ACM (55) (2008). Web SearchBibTeXDownload
311The Search for Equilibrium Concepts. Christos H. Papadimitriou. SAGT 2008, 1-3. Web SearchBibTeXDownload
310Linked 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
309The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. Alex Fabrikant, Christos H. Papadimitriou. SODA 2008, 844-853. Web SearchBibTeXDownload
308The 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
307Some Recent Results in Algorithmic Game Theory. Christos H. Papadimitriou. WINE 2008, 17. Web SearchBibTeXDownload
2007
306Congestion games with malicious players. Moshe Babaioff, Robert Kleinberg, Christos H. Papadimitriou. ACM Conference on Electronic Commerce 2007, 103-112. Web SearchBibTeXDownload
305Progress in approximate nash equilibria. Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou. ACM Conference on Electronic Commerce 2007, 355-358. Web SearchBibTeXDownload
304The 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
303Nash Equilibria: Where We Stand. Christos H. Papadimitriou. ESA 2007, 1. Web SearchBibTeXDownload
302Computing Equilibria in Anonymous Games. Constantinos Daskalakis, Christos H. Papadimitriou. FOCS 2007, 83-93. Web SearchBibTeXDownload
301Balancing 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
300Approximately dominating representatives. Vladlen Koltun, Christos H. Papadimitriou. Theor. Comput. Sci. (371): 148-154 (2007). Web SearchBibTeXDownload
299Incentive-Compatible Interdomain Routing with Linear Utilities. Alexander Hall, Evdokia Nikolova, Christos H. Papadimitriou. WINE 2007, 232-244. Web SearchBibTeXDownload
298The Computation of Equilibria. Christos H. Papadimitriou. WINE 2007, 5-6. Web SearchBibTeXDownload
2006
297Computing 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
296Recognizing Hole-Free 4-Map Graphs in Cubic Time. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. Algorithmica (45): 227-262 (2006). Web SearchBibTeXDownload
295On The Approximability Of The Traveling Salesman Problem. Christos H. Papadimitriou, Santosh Vempala. Combinatorica (26): 101-120 (2006). Web SearchBibTeXDownload
294The 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
293The 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
292Free-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
291On certain connectivity properties of the internet topology. Milena Mihail, Christos H. Papadimitriou, Amin Saberi. J. Comput. Syst. Sci. (72): 239-251 (2006). Web SearchBibTeXDownload
290Reducibility among equilibrium problems. Paul W. Goldberg, Christos H. Papadimitriou. STOC 2006, 61-70. Web SearchBibTeXDownload
289The complexity of computing a Nash equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. STOC 2006, 71-78. Web SearchBibTeXDownload
288A Note on Approximate Nash Equilibria. Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou. WINE 2006, 297-306. Web SearchBibTeXDownload
2005
287Approximating the Distortion. Alexander Hall, Christos H. Papadimitriou. APPROX-RANDOM 2005, 111-122. Web SearchBibTeXDownload
286Games Other People Play. Christos H. Papadimitriou. CONCUR 2005, 5. Web SearchBibTeXDownload
285Algorithmic Problems in Ad Hoc Networks. Christos H. Papadimitriou. DCOSS 2005, 1. Web SearchBibTeXDownload
284A BGP-based mechanism for lowest-cost routing. Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker. Distributed Computing (18): 61-72 (2005). Web SearchBibTeXDownload
283The complexity of computing a Nash equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. Electronic Colloquium on Computational Complexity (ECCC) 2005. Web SearchBibTeXDownload
282Reducibility Among Equilibrium Problems. Paul W. Goldberg, Christos H. Papadimitriou. Electronic Colloquium on Computational Complexity (ECCC) 2005. Web SearchBibTeXDownload
281Three-Player Games Are Hard. Konstantinos Daskalakis, Christos H. Papadimitriou. Electronic Colloquium on Computational Complexity (ECCC) 2005. Web SearchBibTeXDownload
280The Complexity of Games on Highly Regular Graphs. Konstantinos Daskalakis, Christos H. Papadimitriou. ESA 2005, 71-82. Web SearchBibTeXDownload
279Approximately Dominating Representatives. Vladlen Koltun, Christos H. Papadimitriou. ICDT 2005, 204-214. Web SearchBibTeXDownload
278The complexity of low-distortion embeddings between point sets. Christos H. Papadimitriou, Shmuel Safra. SODA 2005, 112-118. Web SearchBibTeXDownload
277Computing equilibria in multi-player games. Christos H. Papadimitriou, Tim Roughgarden. SODA 2005, 82-91. Web SearchBibTeXDownload
276Computing correlated equilibria in multi-player games. Christos H. Papadimitriou, Tim Roughgarden. STOC 2005, 49-56. Web SearchBibTeXDownload
275On a conjecture related to geometric routing. Christos H. Papadimitriou, David Ratajczak. Theor. Comput. Sci. (344): 3-14 (2005). Web SearchBibTeXDownload
274... The Interaction Between Algorithms and Game Theory. Christos H. Papadimitriou. WEA 2005, 1-3. Web SearchBibTeXDownload
273Recent Developments in Equilibria Algorithms. Christos H. Papadimitriou. WINE 2005, 1-2. Web SearchBibTeXDownload
272Experiments with an Economic Model of the Worldwide Web. Georgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri. WINE 2005, 46-54. Web SearchBibTeXDownload
271An 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
270On a Conjecture Related to Geometric Routing. Christos H. Papadimitriou, David Ratajczak. ALGOSENSORS 2004, 9-17. Web SearchBibTeXDownload
269Networks and Games. Christos H. Papadimitriou. HiPC 2004, 7. Web SearchBibTeXDownload
268Segmentation problems. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. J. ACM (51): 263-280 (2004). Web SearchBibTeXDownload
267Global Synchronization in Sensornets. Jeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker. LATIN 2004, 609-624. Web SearchBibTeXDownload
266Selfish 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
265The complexity of pure Nash equilibria. Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar. STOC 2004, 604-612. Web SearchBibTeXDownload
2003
264A 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
263Games and Networks. Christos H. Papadimitriou. FCT 2003, 157. Web SearchBibTeXDownload
262On Certain Connectivity Properties of the Internet Topology. Milena Mihail, Christos H. Papadimitriou, Amin Saberi. FOCS 2003, 28-35. Web SearchBibTeXDownload
261On the complexity of single-rule datalog queries. Georg Gottlob, Christos H. Papadimitriou. Inf. Comput. (183): 104-122 (2003). Web SearchBibTeXDownload
260An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents. Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos. Internet Mathematics (1): 129-150 (2003). Web SearchBibTeXDownload
259Mythematics: storytelling in the teaching of computer science and mathematics. Christos H. Papadimitriou. ITiCSE 2003, 1. Web SearchBibTeXDownload
258Auditing Boolean attributes. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. J. Comput. Syst. Sci. (66): 244-253 (2003). Cited by 91Web SearchBibTeXDownload
257On the complexity of price equilibria. Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra. J. Comput. Syst. Sci. (67): 311-324 (2003). Web SearchBibTeXDownload
256Geographic routing without location information. Ananth Rao, Christos H. Papadimitriou, Scott Shenker, Ion Stoica. MOBICOM 2003, 96-108. Web SearchBibTeXDownload
255The New Problems. Christos H. Papadimitriou. PCK50 2003, 10. Web SearchBibTeX
254On a network creation game. Alex Fabrikant, Ankur Luthra, Elitza N. Maneva, Christos H. Papadimitriou, Scott Shenker. PODC 2003, 347-351. Web SearchBibTeXDownload
253MythematiCS: in praise of storytelling in the teaching of computer science and math. Christos H. Papadimitriou. SIGCSE Bulletin (35): 7-9 (2003). Web SearchBibTeXDownload
252An 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
251Learning the Internet. Christos H. Papadimitriou. COLT 2002, 396. Web SearchBibTeXDownload
250Market Equilibrium via a Primal-Dual-Type Algorithm. Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani. FOCS 2002, 389-395. Web SearchBibTeXDownload
249Heuristically 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
248Map graphs. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. J. ACM (49): 127-138 (2002). Web SearchBibTeXDownload
247On 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
246Special Issue on PODS 1999 - Guest Editors' Foreword. Yannis E. Ioannidis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (64): 441-442 (2002). Web SearchBibTeXDownload
245The Internet, the Web, and Algorithms. Christos H. Papadimitriou. LATIN 2002, 2. Web SearchBibTeXDownload
244A BGP-based mechanism for lowest-cost routing. Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker. PODC 2002, 173-182. Web SearchBibTeXDownload
243On the Eigenvalue Power Law. Milena Mihail, Christos H. Papadimitriou. RANDOM 2002, 254-262. Web SearchBibTeXDownload
242Understanding the Internet. Christos H. Papadimitriou. SETN 2002, 1-2. Web SearchBibTeXDownload
241Selfish 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
240The Joy of Theory. Christos H. Papadimitriou. STOC 2002, 116. Web SearchBibTeXDownload
239On the complexity of equilibria. Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra. STOC 2002, 67-71. Web SearchBibTeXDownload
238A 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
237Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. Christos H. Papadimitriou. FOCS 2001, 4-8. Web SearchBibTeXDownload
236Algorithmic problems related to the Internet. Christos H. Papadimitriou. HERCMA 2001, 92. Web SearchBibTeX
235Algorithms, Games, and the Internet. Christos H. Papadimitriou. ICALP 2001, 1-3. Web SearchBibTeXDownload
234On Approximating a Scheduling Problem. Pierluigi Crescenzi, Xiaotie Deng, Christos H. Papadimitriou. J. Comb. Optim. (5): 287-297 (2001). Web SearchBibTeXDownload
233Sharing the Cost of Multicast Transmissions. Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker. J. Comput. Syst. Sci. (63): 21-41 (2001). Web SearchBibTeXDownload
232Multiobjective Query Optimization. Christos H. Papadimitriou, Mihalis Yannakakis. PODS 2001. Web SearchBibTeXDownload
231Game theory, algorithms, and the Internet. Christos H. Papadimitriou. SODA 2001, 391. Web SearchBibTeXDownload
230Algorithms, games, and the internet. Christos H. Papadimitriou. STOC 2001, 749-753. Web SearchBibTeXDownload
229Deciding 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
228Theoretical Problems Related to the Internet. Christos H. Papadimitriou. COCOON 2000, 1-2. Web SearchBibTeXDownload
227Optimization Problems in Congestion Control. Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker. FOCS 2000, 66-74. Web SearchBibTeXDownload
226On the Approximability of Trade-offs and Optimal Access of Web Sources. Christos H. Papadimitriou, Mihalis Yannakakis. FOCS 2000, 86-92. Web SearchBibTeXDownload
225Latent 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
224Distance-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 SearchBibTeXDownload
223On certain rigorous approaches to data mining (invited talk, abstract only). Christos H. Papadimitriou. KDD 2000, 2. Web SearchBibTeXDownload
222Auditing Boolean Attributes. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. PODS 2000, 86-91. Web SearchBibTeXDownload
221Beyond Competitive Analysis. Elias Koutsoupias, Christos H. Papadimitriou. SIAM J. Comput. (30): 300-317 (2000). Web SearchBibTeXDownload
220On the Difficulty of Designing Good Classifiers. Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou. SIAM J. Comput. (30): 318-323 (2000). Web SearchBibTeXDownload
219Reminiscences 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
218Sharing the cost of muliticast transmissions (preliminary version). Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker. STOC 2000, 218-227. Web SearchBibTeXDownload
217On the approximability of the traveling salesman problem (extended abstract). Christos H. Papadimitriou, Santosh Vempala. STOC 2000, 126-133. Web SearchBibTeXDownload
1999
216Map Graphs. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. CoRR (cs.DM/9910013) (1999). Web SearchBibTeXDownload
215Software 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
214Algorithmic Aspects of Protein Structure Similarity. Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou. FOCS 1999, 512-522. Web SearchBibTeXDownload
213Novel Computational Approaches to Information Retrieval and Data Mining (Abstract). Christos H. Papadimitriou. ICDT 1999, 31. Web SearchBibTeXDownload
212On the Complexity of Database Queries. Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (58): 407-427 (1999). Web SearchBibTeXDownload
211Topological Queries in Spatial Databases. Christos H. Papadimitriou, Dan Suciu, Victor Vianu. J. Comput. Syst. Sci. (58): 29-53 (1999). Cited by 97Web SearchBibTeXDownload
210On the Floyd-Warshall Algorithm for Logic Programs. Christos H. Papadimitriou, Martha Sideri. J. Log. Program. (41): 129-137 (1999). Web SearchBibTeXDownload
209Inferring 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-51 (1999). Web SearchBibTeXDownload
208Exploring an unknown graph. Xiaotie Deng, Christos H. Papadimitriou. Journal of Graph Theory (32): 265-297 (1999). Web SearchBibTeXDownload
207On the Complexity of Single-Rule Datalog Queries. Georg Gottlob, Christos H. Papadimitriou. LPAR 1999, 201-222. Web SearchBibTeXDownload
206Topological Queries. Bart Kuijpers, Victor Vianu. SSD 1999, 3-4. Cited by 4Web SearchBibTeXDownload
205Worst-case Equilibria. Elias Koutsoupias, Christos H. Papadimitriou. STACS 1999, 404-413. Web SearchBibTeXDownload
1998
204Algorithmic Approaches to Information Retrieval and Data Mining (Abstract). Christos H. Papadimitriou. COCOON 1998, 1. Web SearchBibTeXDownload
203Incremental Recompilation of Knowledge. Goran Gogic, Christos H. Papadimitriou, Martha Sideri. CoRR (cs.AI/9801101): 23-37 (1998). Web SearchBibTeXDownload
202A 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
201Reflective Relational Machines. Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu. Inf. Comput. (143): 110-136 (1998). Cited by 13Web SearchBibTeXDownload
200How to Learn an Unknown Environment I: The Rectilinear Case. Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou. J. ACM (45): 215-245 (1998). Web SearchBibTeXDownload
199On the Complexity of Protein Folding. Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis. Journal of Computational Biology (5): 423-465 (1998). Web SearchBibTeXDownload
198Latent Semantic Indexing: A Probabilistic Analysis. Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala. PODS 1998, 159-168. Cited by 463Web SearchBibTeXDownload
197On the complexity of protein folding (abstract). Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis. RECOMB 1998, 61-62. Web SearchBibTeXDownload
196Elements of the Theory of Computation. Harry R. Lewis, Christos H. Papadimitriou. SIGACT News (29): 62-78 (1998). Web SearchBibTeXDownload
195Segmentation Problems. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. STOC 1998, 473-482. Cited by 103Web SearchBibTeXDownload
194Planar Map Graphs. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. STOC 1998, 514-523. Web SearchBibTeXDownload
193On 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
192On Kernels, Defaults and Even Graphs. Yannis Dimopoulos, Vangelis Magirou, Christos H. Papadimitriou. Ann. Math. Artif. Intell. (20): 1-12 (1997). Web SearchBibTeXDownload
191Planar Topological Queries. Christos H. Papadimitriou. CDB 1997, 1-6. Web SearchBibTeXDownload
190NP-Completeness: A Retrospective. Christos H. Papadimitriou. ICALP 1997, 2-6. Web SearchBibTeXDownload
189Decision-Making by Hierarchies of Discordant Agents. Xiaotie Deng, Christos H. Papadimitriou. ISAAC 1997, 183-192. Web SearchBibTeXDownload
188Tie-Breaking Semantics and Structural Totality. Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (54): 48-60 (1997). Web SearchBibTeXDownload
187On the Complexity of Database Queries. Christos H. Papadimitriou, Mihalis Yannakakis. PODS 1997, 12-19. Web SearchBibTeXDownload
186On the Analysis of Indexing Schemes. Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou. PODS 1997, 249-256. Cited by 121Web SearchBibTeXDownload
185Emerging 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
184Panarity, Revisited (Extended Abstract). Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. WADS 1997, 472-473. Web SearchBibTeXDownload
1996
183Competitive Distributed Decision-Making. Xiaotie Deng, Christos H. Papadimitriou. Algorithmica (16): 133-150 (1996). Web SearchBibTeXDownload
182On the Difficulty of Designing Good Classifiers. Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou. COCOON 1996, 273-279. Web SearchBibTeXDownload
181Computational Aspacts of Organization Theory (Extended Abstract). Christos H. Papadimitriou. ESA 1996, 559-564. Web SearchBibTeXDownload
180Searching a Fixed Graph. Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis. ICALP 1996, 280-289. Web SearchBibTeXDownload
179The Complexity of Knowledge Representation. Christos H. Papadimitriou. IEEE Conference on Computational Complexity 1996, 244-248. Web SearchBibTeXDownload
178The 2-Evader Problem. Elias Koutsoupias, Christos H. Papadimitriou. Inf. Process. Lett. (57): 249-252 (1996). Web SearchBibTeXDownload
177On 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
176The Bisection Width of Grid Graphs. Christos H. Papadimitriou, Martha Sideri. Mathematical Systems Theory (29): 97-110 (1996). Web SearchBibTeXDownload
175Topological Queries in Spatial Databases. Christos H. Papadimitriou, Dan Suciu, Victor Vianu. PODS 1996, 81-92. Cited by 97Web SearchBibTeXDownload
174In Memoriam: Paris C. Kanellakis. Pascal Van Hentenryck, Gabriel M. Kuper, Christos H. Papadimitriou, Moshe Y. Vardi. PODS 1996, 79. Cited by 2Web SearchBibTeXDownload
173The 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
172Multimedia 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
171An Approximation Scheme for Planar Graph TSP. Michelangelo Grigni, Elias Koutsoupias, Christos H. Papadimitriou. FOCS 1995, 640-645. Web SearchBibTeXDownload
170Topological Inference. Michelangelo Grigni, Dimitris Papadias, Christos H. Papadimitriou. IJCAI (1) 1995, 901-907. Cited by 161Web SearchBibTeX
169The Comparative Linguistics of Knowledge Representation. Goran Gogic, Henry A. Kautz, Christos H. Papadimitriou, Bart Selman. IJCAI (1) 1995, 862-869. Web SearchBibTeX
168Optimal Information Delivery. Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan. ISAAC 1995, 181-187. Web SearchBibTeXDownload
167On the k-Server Conjecture. Elias Koutsoupias, Christos H. Papadimitriou. J. ACM (42): 971-983 (1995). Web SearchBibTeXDownload
166Database Metatheory: Asking the Big Queries. Christos H. Papadimitriou. PODS 1995, 1-10. Web SearchBibTeXDownload
165Database metatheory: asking the big queries. Christos H. Papadimitriou. SIGACT News (26): 13-30 (1995). Web SearchBibTeXDownload
164Reversible Simulation of Space-Bounded Computations. Pierluigi Crescenzi, Christos H. Papadimitriou. Theor. Comput. Sci. (143): 159-165 (1995). Web SearchBibTeXDownload
1994
163Incremental Recompilation of Knowledge. Goran Gogic, Christos H. Papadimitriou, Martha Sideri. AAAI 1994, 922-927. Web SearchBibTeXDownload
162Designing Secure Communication Protocols from Trust Specification. Christos H. Papadimitriou, P. Venkat Rangan, Martha Sideri. Algorithmica (11): 485-499 (1994). Web SearchBibTeXDownload
161Default Theories that Always Have Extensions. Christos H. Papadimitriou, Martha Sideri. Artif. Intell. (69): 347-357 (1994). Web SearchBibTeXDownload
160On the Random Walk Method for Protocol Testing. Milena Mihail, Christos H. Papadimitriou. CAV 1994, 132-141. Web SearchBibTeXDownload
159Motion Planning on a Graph (Extended Abstract). Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki. FOCS 1994, 511-520. Web SearchBibTeXDownload
158Beyond Competitive Analysis. Elias Koutsoupias, Christos H. Papadimitriou. FOCS 1994, 394-400. Web SearchBibTeXDownload
157Information 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
156On 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
155The Power of Reflective Relational Machines. Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu. LICS 1994, 230-240. Cited by 21Web SearchBibTeXDownload
154The 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
153On complexity as bounded rationality (extended abstract). Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1994, 726-733. Web SearchBibTeXDownload
152The Complexity of Optimal Queueing Network Control. Christos H. Papadimitriou, John N. Tsitsiklis. Structure in Complexity Theory Conference 1994, 318-322. Web SearchBibTeXDownload
1993
151Computing the Throughput of a Network with Dedicated Lines. Christos H. Papadimitriou, Paolo Serafini, Mihalis Yannakakis. Discrete Applied Mathematics (42): 271-278 (1993). Web SearchBibTeXDownload
150On Horn Envelopes and Hypergraph Transversals. Dimitris J. Kavvadias, Christos H. Papadimitriou, Martha Sideri. ISAAC 1993, 399-405. Web SearchBibTeXDownload
149The Parallel Complexity of Simple Logic Programs. Foto N. Afrati, Christos H. Papadimitriou. J. ACM (40): 891-916 (1993). Cited by 13Web SearchBibTeXDownload
148Linear programming without the matrix. Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1993, 121-129. Web SearchBibTeXDownload
147On 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 SearchBibTeXDownload
1992
146On Finding Extensions of Default Theories. Christos H. Papadimitriou, Martha Sideri. ICDT 1992, 276-281. Web SearchBibTeXDownload
145Competitive Distributed Decision-Making. Xiaotie Deng, Christos H. Papadimitriou. IFIP Congress (1) 1992, 350-356. Web SearchBibTeX
144On the Optimal Bisection of a Polygon. Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri. INFORMS Journal on Computing (4): 435-438 (1992). Web SearchBibTeXDownload
143On the Greedy Algorithm for Satisfiability. Elias Koutsoupias, Christos H. Papadimitriou. Inf. Process. Lett. (43): 53-55 (1992). Web SearchBibTeXDownload
142Tie-Breaking Semantics and Structural Totality. Christos H. Papadimitriou, Mihalis Yannakakis. PODS 1992, 16-22. Web SearchBibTeXDownload
141The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem. Christos H. Papadimitriou. SIAM J. Comput. (21): 450-465 (1992). Web SearchBibTeXDownload
140The 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
139On Selecting a Satisfying Truth Assignment (Extended Abstract). Christos H. Papadimitriou. FOCS 1991, 163-169. Web SearchBibTeXDownload
138How to Learn an Unknown Environment (Extended Abstract). Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou. FOCS 1991, 298-303. Web SearchBibTeXDownload
137Designing Secure Communication Protocols from Trust Specifications. Christos H. Papadimitriou, P. Venkat Rangan, Martha Sideri. FSTTCS 1991, 360-368. Web SearchBibTeXDownload
136Decision-Making with Incomplete Information. Christos H. Papadimitriou. ISA 1991, 1. Web SearchBibTeXDownload
135The 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
134Modularity of Cycles and Paths in Graphs. Esther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis. J. ACM (38): 255-274 (1991). Web SearchBibTeXDownload
133Why not Negation by Fixpoint?. Phokion G. Kolaitis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (43): 125-144 (1991). Web SearchBibTeXDownload
132Optimization, Approximation, and Complexity Classes. Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (43): 425-440 (1991). Web SearchBibTeXDownload
131On path lengths modulo three. Xiaotie Deng, Christos H. Papadimitriou. Journal of Graph Theory (15): 267-282 (1991). Web SearchBibTeXDownload
130Optimal Coteries. Christos H. Papadimitriou, Martha Sideri. PODC 1991, 75-80. Web SearchBibTeXDownload
129On the Value of Information in Distributed Decision-Making (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. PODC 1991, 61-64. Web SearchBibTeXDownload
128Shortest Paths Without a Map. Christos H. Papadimitriou, Mihalis Yannakakis. Theor. Comput. Sci. (84): 127-150 (1991). Web SearchBibTeXDownload
127On Total Functions, Existence Theorems and Computational Complexity. Nimrod Megiddo, Christos H. Papadimitriou. Theor. Comput. Sci. (81): 317-324 (1991). Web SearchBibTeXDownload
1990
126A Linear Programming Approach to Reasoning about Probabilities. Dimitris J. Kavvadias, Christos H. Papadimitriou. Ann. Math. Artif. Intell. (1): 189-205 (1990). Web SearchBibTeXDownload
125On recognizing integer polyhedra. Christos H. Papadimitriou, Mihalis Yannakakis. Combinatorica (10): 107-109 (1990). Web SearchBibTeXDownload
124On the Predictability of Coupled Automata: An Allegory about Chaos. Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis. FOCS 1990, 788-793. Web SearchBibTeXDownload
123On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract). Christos H. Papadimitriou. FOCS 1990, 794-801. Web SearchBibTeXDownload
122Exploring an Unknown Graph (Extended Abstract). Xiaotie Deng, Christos H. Papadimitriou. FOCS 1990, 355-361. Web SearchBibTeXDownload
121The Geometry of Grasping. Xanthippi Markenscoff, Luqun Ni, Christos H. Papadimitriou. I. J. Robotic Res. (9): 61-74 (1990). Web SearchBibTeXDownload
120The 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
119Some Computational Aspects of Circumscription. Phokion G. Kolaitis, Christos H. Papadimitriou. J. ACM (37): 1-14 (1990). Web SearchBibTeXDownload
118Towards an Architecture-Independent Analysis of Parallel Algorithms. Christos H. Papadimitriou, Mihalis Yannakakis. SIAM J. Comput. (19): 322-328 (1990). Web SearchBibTeXDownload
117The Bisection Width of Grid Graphs. Christos H. Papadimitriou, Martha Sideri. SODA 1990, 405-410. Web SearchBibTeXDownload
116On the Complexity of Local Search (Extended Abstract). Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis. STOC 1990, 438-445. Web SearchBibTeXDownload
115On 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
114Shortest Paths Without a Map. Christos H. Papadimitriou, Mihalis Yannakakis. ICALP 1989, 610-620. Web SearchBibTeXDownload
113Optimum Grip of a Polygon. Xanthippi Markenscoff, Christos H. Papadimitriou. I. J. Robotic Res. (8): 17-29 (1989). Web SearchBibTeXDownload
112Corrigendum: The Complexity of Cubical Graphs. Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou. Inf. Comput. (82): 350-353 (1989). Web SearchBibTeXDownload
111Finding Feasible Paths for a Two-Point Body. Ellen B. Feinberg, Christos H. Papadimitriou. J. Algorithms (10): 109-119 (1989). Web SearchBibTeXDownload
110Exponential lower bounds for finding Brouwer fix points. Michael D. Hirsch, Christos H. Papadimitriou, Stephen A. Vavasis. J. Complexity (5): 379-416 (1989). Web SearchBibTeXDownload
109On 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
108Some Computational Aspects of Circumscription. Phokion G. Kolaitis, Christos H. Papadimitriou. AAAI 1988, 455-469. Web SearchBibTeXDownload
107The Synthesis of Communication Protocols. Foto N. Afrati, Christos H. Papadimitriou, Georgios I. Papadimitriou. Algorithmica (3): 451-472 (1988). Cited by 5Web SearchBibTeXDownload
106Scheduling Dags to Minimize Time and Communication. Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou. AWOC 1988, 134-138. Cited by 11Web SearchBibTeXDownload
105Complexity Characterizations of Attribute Grammar Languages. Sophocles Ephremidis, Christos H. Papadimitriou, Martha Sideri. Inf. Comput. (78): 178-186 (1988). Web SearchBibTeXDownload
104On Generating All Maximal Independent Sets. David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis. Inf. Process. Lett. (27): 119-123 (1988). Web SearchBibTeXDownload
103The 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
102Probabilistic satisfiability. George F. Georgakopoulos, Dimitris J. Kavvadias, Christos H. Papadimitriou. J. Complexity (4): 1-11 (1988). Web SearchBibTeXDownload
101How Easy is Local Search?. David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (37): 79-100 (1988). Web SearchBibTeXDownload
100The Complexity of Facets Resolved. Christos H. Papadimitriou, David Wolfe. J. Comput. Syst. Sci. (37): 2-13 (1988). Web SearchBibTeXDownload
99The Complexity of Recognizing Polyhedral Scenes. Lefteris M. Kirousis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (37): 14-38 (1988). Web SearchBibTeXDownload
98Why Not Negation by Fixpoint?. Phokion G. Kolaitis, Christos H. Papadimitriou. PODS 1988, 231-239. Web SearchBibTeXDownload
97Optimization, Approximation, and Complexity Classes (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1988, 229-234. Web SearchBibTeXDownload
96Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1988, 510-513. Web SearchBibTeXDownload
1987
95Optimal Piecewise Linear Motion of an Object Among Obstacles. Christos H. Papadimitriou, Ellen B. Silverberg. Algorithmica (2): 523-539 (1987). Web SearchBibTeXDownload
94The 1-Steiner Tree Problem. George K. Georgakopoulos, Christos H. Papadimitriou. J. Algorithms (8): 122-130 (1987). Web SearchBibTeXDownload
93The Parallel Complexity of Simple Chain Queries. Foto N. Afrati, Christos H. Papadimitriou. PODS 1987, 210-213. Cited by 40Web SearchBibTeXDownload
92On Stochastic Scheduling with In-Tree Precedence Constraints. Christos H. Papadimitriou, John N. Tsitsiklis. SIAM J. Comput. (16): 1-6 (1987). Web SearchBibTeXDownload
91The Discrete Geodesic Problem. Joseph S. B. Mitchell, David M. Mount, Christos H. Papadimitriou. SIAM J. Comput. (16): 647-668 (1987). Web SearchBibTeXDownload
90The Complexity of Reliable Concurrency Control. Christos H. Papadimitriou, Mihalis Yannakakis. SIAM J. Comput. (16): 538-553 (1987). Web SearchBibTeXDownload
89A Communication-Time Tradeoff. Christos H. Papadimitriou, Jeffrey D. Ullman. SIAM J. Comput. (16): 639-646 (1987). Cited by 85Web SearchBibTeXDownload
88Complexity characterizations of attribute grammar languages. Sophocles Ephremidis, Christos H. Papadimitriou, Martha Sideri. Structure in Complexity Theory Conference 1987. Web SearchBibTeX
87The Weighted Region Problem. Joseph S. B. Mitchell, Christos H. Papadimitriou. Symposium on Computational Geometry 1987, 30-38. Web SearchBibTeXDownload
1986
86Shortest-Path Motion. Christos H. Papadimitriou. FSTTCS 1986, 144-153. Web SearchBibTeXDownload
85A Note on Succinct Representations of Graphs. Christos H. Papadimitriou, Mihalis Yannakakis. Information and Control (71): 181-185 (1986). Web SearchBibTeXDownload
84The 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
83The performance of a precedence-based queuing discipline. John N. Tsitsiklis, Christos H. Papadimitriou, Pierre A. Humblet. J. ACM (33): 593-602 (1986). Web SearchBibTeXDownload
82On the Complexity of Circulations. Esther M. Arkin, Christos H. Papadimitriou. J. Algorithms (7): 134-145 (1986). Web SearchBibTeXDownload
81Algorithmic Aspects of Multiversion Concurrency Control. Thanasis Hadzilacos, Christos H. Papadimitriou. J. Comput. Syst. Sci. (33): 297-310 (1986). Web SearchBibTeXDownload
80The Synthesis of Communication Protocols. Foto N. Afrati, Christos H. Papadimitriou, Georgios I. Papadimitriou. PODC 1986, 263-271. Cited by 5Web SearchBibTeXDownload
79Convergence 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 SearchBibTeXDownload
78Searching and Pebbling. Lefteris M. Kirousis, Christos H. Papadimitriou. Theor. Comput. Sci. (47): 205-218 (1986). Web SearchBibTeXDownload
1985
77A note the expressive power of Prolog. Christos H. Papadimitriou. Bulletin of the EATCS (26): 21-22 (1985). Web SearchBibTeX
76Interval graphs and seatching. Lefteris M. Kirousis, Christos H. Papadimitriou. Discrete Mathematics (55): 181-184 (1985). Web SearchBibTeXDownload
75The Complexity of Recognizing Polyhedral Scenes (Extended Abstract). Lefteris M. Kirousis, Christos H. Papadimitriou. FOCS 1985, 175-185. Web SearchBibTeXDownload
74The Complexity of Facets Resolved. Christos H. Papadimitriou, David Wolfe. FOCS 1985, 74-78. Web SearchBibTeXDownload
73How Easy Is Local Search? (Extended Abstract). David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis. FOCS 1985, 39-42. Web SearchBibTeXDownload
72The Complexity of Cubical Graphs. Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou. Information and Control (66): 53-60 (1985). Cited by 13Web SearchBibTeXDownload
71An Algorithm for Shortest-Path Motion in Three Dimensions. Christos H. Papadimitriou. Inf. Process. Lett. (20): 259-263 (1985). Web SearchBibTeXDownload
70Correction to ``A Theorem in Database Concurrency Control''. Christos H. Papadimitriou. J. ACM (32): 750 (1985). Web SearchBibTeX
69Correction to "A Theorem in Database Concurrency Control". Christos H. Papadimitriou. J. ACM (32): 750 (1985). Web SearchBibTeX
68Games Against Nature. Christos H. Papadimitriou. J. Comput. Syst. Sci. (31): 288-301 (1985). Web SearchBibTeXDownload
67Algorithmic Aspects of Multiversion Concurrency Control. Thanasis Hadzilacos, Christos H. Papadimitriou. PODS 1985, 96-104. Web SearchBibTeXDownload
66The Complexity of Reliable Concurrency Control. Christos H. Papadimitriou, Mihalis Yannakakis. PODS 1985, 230-234. Web SearchBibTeXDownload
65The Complexity of Distributed Concurrency Control. Paris C. Kanellakis, Christos H. Papadimitriou. SIAM J. Comput. (14): 52-74 (1985). Web SearchBibTeXDownload
1984
64On Concurrency Control by Multiple Versions. Christos H. Papadimitriou, Paris C. Kanellakis. ACM Trans. Database Syst. (9): 89-99 (1984). Web SearchBibTeXDownload
63A Communication-Time Tradeoff. Christos H. Papadimitriou, Jeffrey D. Ullman. FOCS 1984, 84-88. Cited by 85Web SearchBibTeXDownload
62The Complexity of Cubical Graphs (Extended Abstract). Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou. ICALP 1984, 51-57. Web SearchBibTeXDownload
61Updates of Relational Views. Stavros S. Cosmadakis, Christos H. Papadimitriou. J. ACM (31): 742-760 (1984). Web SearchBibTeXDownload
60On the complexity of unique solutions. Christos H. Papadimitriou. J. ACM (31): 392-400 (1984). Web SearchBibTeXDownload
59On Two Geometric Problems Related to the Traveling Salesman Problem. Christos H. Papadimitriou, Umesh V. Vazirani. J. Algorithms (5): 231-246 (1984). Web SearchBibTeXDownload
58Inclusion 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
57Is Distributed Locking Harder?. Paris C. Kanellakis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (28): 103-120 (1984). Web SearchBibTeXDownload
56Communication Complexity. Dömötör Pálvölgyi, Michael Sipser. J. Comput. Syst. Sci. (28): 260-269 (1984). Web SearchBibTeXDownload
55The Complexity of Facets (and Some Facets of Complexity). Christos H. Papadimitriou, Mihalis Yannakakis. J. Comput. Syst. Sci. (28): 244-259 (1984). Web SearchBibTeXDownload
54The even-path problem for graphs and digraphs. Andrea S. Lapaugh, Christos H. Papadimitriou. Networks (14): 507-513 (1984). Web SearchBibTeXDownload
53The 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
52An Optimality Theory of Concurrency Control for Databases. H. T. Kung, Christos H. Papadimitriou. Acta Inf. (19): 1-11 (1983). Web SearchBibTeXDownload
51Topological Bandwidth. Fillia Makedon, Christos H. Papadimitriou, Ivan Hal Sudborough. CAAP 1983, 317-331. Web SearchBibTeXDownload
50Games Against Nature (Extended Abstract). Christos H. Papadimitriou. FOCS 1983, 446-450. Web SearchBibTeXDownload
49Cutting 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
48Updates of Relational Views. Stavros S. Cosmadakis, Christos H. Papadimitriou. PODS 1983, 317-331. Web SearchBibTeXDownload
47Concurrency Control by Locking. Christos H. Papadimitriou. SIAM J. Comput. (12): 215-226 (1983). Web SearchBibTeXDownload
46Two remarks on the power of counting. Christos H. Papadimitriou, Stathis Zachos. Theoretical Computer Science 1983, 269-276. Web SearchBibTeXDownload
45Theory of concurrency control. Christos H. Papadimitriou. Theoretical Computer Science 1983, 35-47. Web SearchBibTeXDownload
1982
44On the Complexity of Unique Solutions. Christos H. Papadimitriou. FOCS 1982, 14-20. Web SearchBibTeXDownload
43On the Complexity of Designing Distributed Protocols. Christos H. Papadimitriou, John N. Tsitsiklis. Information and Control (53): 211-218 (1982). Web SearchBibTeXDownload
42The complexity of restricted spanning tree problems. Christos H. Papadimitriou, Mihalis Yannakakis. J. ACM (29): 285-309 (1982). Web SearchBibTeXDownload
41A theorem in database concurrency control. Christos H. Papadimitriou. J. ACM (29): 998-1006 (1982). Web SearchBibTeXDownload
40Algebraic Dependencies. Mihalis Yannakakis, Christos H. Papadimitriou. J. Comput. Syst. Sci. (25): 2-41 (1982). Web SearchBibTeXDownload
39Inclusion Dependencies and Their Interaction with Functional Dependencies. Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou. PODS 1982, 171-176. Web SearchBibTeXDownload
38On Concurrency Control by Multiple Versions. Christos H. Papadimitriou, Paris C. Kanellakis. PODS 1982, 76-82. Web SearchBibTeXDownload
37Is Distributed Locking Harder?. Paris C. Kanellakis, Christos H. Papadimitriou. PODS 1982, 98-107. Web SearchBibTeXDownload
36On Linear Characterizations of Combinatorial Optimization Problems. Richard M. Karp, Christos H. Papadimitriou. SIAM J. Comput. (11): 620-632 (1982). Web SearchBibTeXDownload
35Hamilton Paths in Grid Graphs. Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter. SIAM J. Comput. (11): 676-686 (1982). Web SearchBibTeXDownload
34The Complexity of Facets (and Some Facets of Complexity). Christos H. Papadimitriou, Mihalis Yannakakis. STOC 1982, 255-260. Web SearchBibTeXDownload
33Communication Complexity. Dömötör Pálvölgyi, Michael Sipser. STOC 1982, 196-200. Web SearchBibTeXDownload
32Symmetric Space-Bounded Computation. Harry R. Lewis, Christos H. Papadimitriou. Theor. Comput. Sci. (19): 161-187 (1982). Web SearchBibTeXDownload
1981
31The Complexity of Distributed Concurrency Control. Paris C. Kanellakis, Christos H. Papadimitriou. FOCS 1981, 185-197. Web SearchBibTeXDownload
30The 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
29Worst-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
28On Minimal Eulerian Graphs. Christos H. Papadimitriou, Mihalis Yannakakis. Inf. Process. Lett. (12): 203-205 (1981). Web SearchBibTeXDownload
27The Clique Problem for Planar Graphs. Christos H. Papadimitriou, Mihalis Yannakakis. Inf. Process. Lett. (13): 131-133 (1981). Web SearchBibTeXDownload
26The 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
25On the complexity of integer programming. Christos H. Papadimitriou. J. ACM (28): 765-768 (1981). Web SearchBibTeXDownload
24A 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
23Covering Graphs by Simple Circuits. Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael Rodeh. SIAM J. Comput. (10): 746-750 (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
21On the Power of Locking. Christos H. Papadimitriou. SIGMOD Conference 1981, 148-154. Web SearchBibTeXDownload
1980
20On 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
19On Linear Characterizations of Combinatorial Optimization Problems. Richard M. Karp, Christos H. Papadimitriou. FOCS 1980, 1-9. Web SearchBibTeXDownload
18Algebraic Dependencies (Extended Abstract). Mihalis Yannakakis, Christos H. Papadimitriou. FOCS 1980, 328-332. Web SearchBibTeXDownload
17Symmetric Space-Bounded Computation (Extended Abstract). Harry R. Lewis, Christos H. Papadimitriou. ICALP 1980, 374-384. Web SearchBibTeXDownload
16A Worst-Case Analysis of Nearest Neighbor Searching by Projection. Christos H. Papadimitriou, Jon Louis Bentley. ICALP 1980, 470-482. Web SearchBibTeXDownload
15Flowshop scheduling with limited temporary storage. Christos H. Papadimitriou, Paris C. Kanellakis. J. ACM (27): 533-549 (1980). Web SearchBibTeXDownload
1979
14Locking Policies: Safety and Freedom from Deadlock. Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung. FOCS 1979, 286-297. Web SearchBibTeXDownload
13The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). Christos H. Papadimitriou, Mihalis Yannakakis. ICALP 1979, 460-470. Web SearchBibTeXDownload
12Efficient Search for Rationals. Christos H. Papadimitriou. Inf. Process. Lett. (8): 1-4 (1979). Web SearchBibTeXDownload
11The serializability of concurrent database updates. Christos H. Papadimitriou. J. ACM (26): 631-653 (1979). Web SearchBibTeXDownload
10Optimality of the Fast Fourier transform. Christos H. Papadimitriou. J. ACM (26): 95-102 (1979). Web SearchBibTeXDownload
9Scheduling Interval-Ordered Tasks. Christos H. Papadimitriou, Mihalis Yannakakis. SIAM J. Comput. (8): 405-409 (1979). Web SearchBibTeXDownload
8An Optimality Theory of Concurrency Control for Databases. H. T. Kung, Christos H. Papadimitriou. SIGMOD Conference 1979, 116-126. Web SearchBibTeXDownload
1978
7The 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
6The complexity of the capacitated tree problem. Christos H. Papadimitriou. Networks (8): 217-230 (1978). Web 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
Developed by the Database Group at the University of Wisconsin and Yahoo! Research