default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDChristos H. Papadimitriou
Christos Harilaos Papadimitriou – Χρήστος Χαρίλαος Παπαδημητρίου
Person information
- unicode name: Χρήστος Χαρίλαος Παπαδημητρίου
- affiliation: Columbia University, New York, NY, USA
- affiliation (former): University of California, Berkeley, USA
- award (2016): IEEE John von Neumann Medal
- award (2012): Gödel Prize
- award (2002): Knuth Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2008
[b8]Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh V. Vazirani:
Algorithms. McGraw-Hill 2008, ISBN 978-0-07-352340-8, pp. I-X, 1-320- 2007
- [b7]Christos H. Papadimitriou:
Computational complexity. Academic Internet Publ. 2007, ISBN 978-1-4288-1409-7, pp. 1-49 - 2005
- [b6]Christos H. Papadimitriou:
Turing - a novel about computation. MIT Press 2005, ISBN 978-0-262-66191-1, pp. 1-284 - 1998
- [b5]Harry R. Lewis, Christos H. Papadimitriou:
Elements of the theory of computation, 2nd Edition. Prentice Hall 1998, ISBN 978-0-13-262478-7, pp. 1-361 - 1994
- [b4]Christos H. Papadimitriou:
Computational complexity. Addison-Wesley 1994, ISBN 978-0-201-53082-7, pp. I-XV, 1-523 - 1986
- [b3]Christos H. Papadimitriou:
The Theory of Database Concurrency Control. Computer Science Press 1986, ISBN 0-88175-027-1 - 1982
- [b2]Christos H. Papadimitriou, Kenneth Steiglitz:
Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall 1982, ISBN 0-13-152462-3 - 1981
- [b1]Harry R. Lewis, Christos H. Papadimitriou:
Elements of the Theory of Computation. Prentice-Hall 1981, ISBN 0-13-273417-6, pp. I-XIV, 1-466
Journal Articles
- 2024
- [j183]Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc:
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. Math. Oper. Res. 49(3): 1607-1628 (2024) - 2023
- [j182]Christos H. Papadimitriou, Binghui Peng:
Public goods games in directed networks. Games Econ. Behav. 139: 161-179 (2023) - 2022
- [j181]Christos H. Papadimitriou, George Pierrakos, Alexandros Psomas, Aviad Rubinstein:
On the complexity of dynamic mechanism design. Games Econ. Behav. 134: 399-427 (2022) - [j180]Christos H. Papadimitriou, Angela D. Friederici:
Bridging the Gap Between Neurons and Cognition Through Assemblies of Neurons. Neural Comput. 34(2): 291-306 (2022) - 2019
- [j179]Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, Aviad Rubinstein:
Reductions in PPP. Inf. Process. Lett. 145: 48-52 (2019) - 2018
- [j178]Christos H. Papadimitriou:
The EATCS Award 2019 - Call for Nominations. Bull. EATCS 126 (2018) - [j177]Christos H. Papadimitriou, Georgios Piliouras
:
From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory. Entropy 20(10): 782 (2018) - [j176]Paul W. Goldberg, Christos H. Papadimitriou:
Towards a unified complexity theory of total functions. J. Comput. Syst. Sci. 94: 167-192 (2018) - [j175]Christos H. Papadimitriou, Georgios Piliouras:
Game dynamics as the meaning of a game. SIGecom Exch. 16(2): 53-63 (2018) - 2017
- [j174]Fedor V. Fomin, Christos H. Papadimitriou, Jean-Eric Pin:
The EATCS Award 2017 - Laudatio for Eva Tardos. Bull. EATCS 121 (2017) - 2016
- [j173]Adi Livnat, Christos H. Papadimitriou:
Sex as an algorithm: the theory of evolution under the lens of computation. Commun. ACM 59(11): 84-93 (2016) - [j172]Yang Cai, Ozan Candogan, Constantinos Daskalakis, Christos H. Papadimitriou:
Zero-Sum Polymatrix Games: A Generalization of Minmax. Math. Oper. Res. 41(2): 648-655 (2016) - [j171]Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein:
The Complexity of Fairness Through Equilibrium. ACM Trans. Economics and Comput. 4(4): 20:1-20:19 (2016) - 2015
- [j170]Christos H. Papadimitriou, George Pierrakos:
Optimal deterministic auctions with correlated priors. Games Econ. Behav. 92: 430-454 (2015) - [j169]Constantinos Daskalakis, Christos H. Papadimitriou:
Approximate Nash equilibria in anonymous games. J. Econ. Theory 156: 207-245 (2015) - 2014
- [j168]Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:
Algorithms, games, and evolution. Proc. Natl. Acad. Sci. USA 111(29): 10620-10623 (2014) - 2013
- [j167]Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani:
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. ACM Trans. Economics and Comput. 1(2): 9:1-9:25 (2013) - 2012
- [j166]Christos H. Papadimitriou:
Alan and I. Commun. ACM 55(9): 42-43 (2012) - 2011
- [j165]Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno:
On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12-14): 1054-1065 (2011) - 2010
- [j164]Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou:
The myth of the Folk Theorem. Games Econ. Behav. 70(1): 34-43 (2010) - [j163]Christos H. Papadimitriou, Mihalis Yannakakis:
An impossibility theorem for price-adjustment mechanisms. Proc. Natl. Acad. Sci. USA 107(5): 1854-1859 (2010) - 2009
- [j162]Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
The complexity of computing a Nash equilibrium. Commun. ACM 52(2): 89-97 (2009) - [j161]Elias Koutsoupias, Christos H. Papadimitriou:
Worst-case equilibria. Comput. Sci. Rev. 3(2): 65-69 (2009) - [j160]Anthony Spatharis, Ilias Foudalis, Martha Sideri, Christos H. Papadimitriou:
Comparing Trade-off Based Models of the Internet. Fundam. Informaticae 92(4): 363-372 (2009) - [j159]Moshe Babaioff, Robert Kleinberg, Christos H. Papadimitriou:
Congestion games with malicious players. Games Econ. Behav. 67(1): 22-35 (2009) - [j158]Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. SIAM J. Comput. 38(6): 2330-2355 (2009) - [j157]Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
The Complexity of Computing a Nash Equilibrium. SIAM J. Comput. 39(1): 195-259 (2009) - [j156]Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou:
A note on approximate Nash equilibria. Theor. Comput. Sci. 410(17): 1581-1588 (2009) - 2008
- [j155]Alexander Hall, Evdokia Nikolova, Christos H. Papadimitriou:
Incentive-Compatible Interdomain Routing with Linear Utilities. Internet Math. 5(4): 395-410 (2008) - [j154]Christos H. Papadimitriou, Tim Roughgarden:
Computing correlated equilibria in multi-player games. J. ACM 55(3): 14:1-14:29 (2008) - [j153]Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani:
Market equilibrium via a primal-dual algorithm for a convex program. J. ACM 55(5): 22:1-22:18 (2008) - 2007
- [j152]Vladlen Koltun, Christos H. Papadimitriou:
Approximately dominating representatives. Theor. Comput. Sci. 371(3): 148-154 (2007) - 2006
- [j151]Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou:
Recognizing Hole-Free 4-Map Graphs in Cubic Time. Algorithmica 45(2): 227-262 (2006) - [j150]Christos H. Papadimitriou, Santosh S. Vempala:
On The Approximability Of The Traveling Salesman Problem. Comb. 26(1): 101-120 (2006) - [j149]Milena Mihail, Christos H. Papadimitriou, Amin Saberi:
On certain connectivity properties of the internet topology. J. Comput. Syst. Sci. 72(2): 239-251 (2006) - [j148]Michal Feldman, Christos H. Papadimitriou, John Chuang, Ion Stoica:
Free-riding and whitewashing in peer-to-peer systems. IEEE J. Sel. Areas Commun. 24(5): 1010-1019 (2006) - 2005
- [j147]Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker:
A BGP-based mechanism for lowest-cost routing. Distributed Comput. 18(1): 61-72 (2005) - [j146]Christos H. Papadimitriou, David Ratajczak:
On a conjecture related to geometric routing. Theor. Comput. Sci. 344(1): 3-14 (2005) - 2004
- [j145]Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
Segmentation problems. J. ACM 51(2): 263-280 (2004) - 2003
- [j144]Georg Gottlob, Christos H. Papadimitriou:
On the complexity of single-rule datalog queries. Inf. Comput. 183(1): 104-122 (2003) - [j143]Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos:
An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents. Internet Math. 1(2): 129-150 (2003) - [j142]Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
Auditing Boolean attributes. J. Comput. Syst. Sci. 66(1): 244-253 (2003) - [j141]Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra:
On the complexity of price equilibria. J. Comput. Syst. Sci. 67(2): 311-324 (2003) - [j140]Christos H. Papadimitriou:
MythematiCS: in praise of storytelling in the teaching of computer science and math. ACM SIGCSE Bull. 35(4): 7-9 (2003) - [j139]Richard M. Karp, Scott Shenker, Christos H. Papadimitriou:
A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 28: 51-55 (2003) - 2002
- [j138]Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, Vasilis Samoladas:
On a model of indexability and its bounds for range queries. J. ACM 49(1): 35-55 (2002) - [j137]Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou:
Map graphs. J. ACM 49(2): 127-138 (2002) - [j136]Yannis E. Ioannidis, Christos H. Papadimitriou:
Special Issue on PODS 1999 - Guest Editors' Foreword. J. Comput. Syst. Sci. 64(3): 441-442 (2002) - [j135]Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning:
A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search. Theor. Comput. Sci. 289(1): 69-83 (2002) - 2001
- [j134]Pierluigi Crescenzi, Xiaotie Deng, Christos H. Papadimitriou:
On Approximating a Scheduling Problem. J. Comb. Optim. 5(3): 287-297 (2001) - [j133]Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker:
Sharing the Cost of Multicast Transmissions. J. Comput. Syst. Sci. 63(1): 21-41 (2001) - [j132]Vincent D. Blondel, Olivier Bournez, Pascal Koiran, Christos H. Papadimitriou, John N. Tsitsiklis:
Deciding stability and mortality of piecewise affine dynamical systems. Theor. Comput. Sci. 255(1-2): 687-696 (2001) - 2000
- [j131]Richard Desper, Feng Jiang, Olli-P. Kallioniemi, Holger Moch, Christos H. Papadimitriou, Alejandro A. Schäffer:
Distance-Based Reconstruction of Tree Models for Oncogenesis. J. Comput. Biol. 7(6): 789-803 (2000) - [j130]Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh S. Vempala:
Latent Semantic Indexing: A Probabilistic Analysis. J. Comput. Syst. Sci. 61(2): 217-235 (2000) - [j129]Elias Koutsoupias, Christos H. Papadimitriou:
Beyond Competitive Analysis. SIAM J. Comput. 30(1): 300-317 (2000) - [j128]Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou:
On the Difficulty of Designing Good Classifiers. SIAM J. Comput. 30(1): 318-323 (2000) - [j127]Kenneth A. Ross, Yannis E. Ioannidis, Anant Jhingran, Christos H. Papadimitriou:
Reminiscences on Influential Papers. SIGMOD Rec. 29(4): 48-49 (2000) - 1999
- [j126]Richard Desper, Feng Jiang, Olli-P. Kallioniemi, Holger Moch, Christos H. Papadimitriou, Alejandro A. Schäffer:
Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data. J. Comput. Biol. 6(1): 37-51 (1999) - [j125]Christos H. Papadimitriou, Dan Suciu, Victor Vianu:
Topological Queries in Spatial Databases. J. Comput. Syst. Sci. 58(1): 29-53 (1999) - [j124]Christos H. Papadimitriou, Mihalis Yannakakis:
On the Complexity of Database Queries. J. Comput. Syst. Sci. 58(3): 407-427 (1999) - [j123]Xiaotie Deng, Christos H. Papadimitriou:
Exploring an unknown graph. J. Graph Theory 32(3): 265-297 (1999) - [j122]Christos H. Papadimitriou, Martha Sideri:
On the Floyd-Warshall Algorithm for Logic Programs. J. Log. Program. 41(1): 129-137 (1999) - [j121]Christos H. Papadimitriou, John N. Tsitsiklis:
The Complexity of Optimal Queuing Network Control. Math. Oper. Res. 24(2): 293-305 (1999) - [j120]Xiaotie Deng, Christos H. Papadimitriou:
Decision-making by hierarchies of discordant agents. Math. Program. 86(2): 417-431 (1999) - 1998
- [j119]Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
A Microeconomic View of Data Mining. Data Min. Knowl. Discov. 2(4): 311-324 (1998) - [j118]Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu:
Reflective Relational Machines. Inf. Comput. 143(2): 110-136 (1998) - [j117]Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou:
How to Learn an Unknown Environment I: The Rectilinear Case. J. ACM 45(2): 215-245 (1998) - [j116]Goran Gogic, Christos H. Papadimitriou, Martha Sideri:
Incremental Recompilation of Knowledge. J. Artif. Intell. Res. 8: 23-37 (1998) - [j115]Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis:
On the Complexity of Protein Folding. J. Comput. Biol. 5(3): 423-465 (1998) - [j114]Harry R. Lewis, Christos H. Papadimitriou:
Elements of the Theory of Computation. SIGACT News 29(3): 62-78 (1998) - 1997
- [j113]Yannis Dimopoulos, Vangelis Magirou, Christos H. Papadimitriou:
On Kernels, Defaults and Even Graphs. Ann. Math. Artif. Intell. 20(1-4): 1-12 (1997) - [j112]Christos H. Papadimitriou, Mihalis Yannakakis:
Tie-Breaking Semantics and Structural Totality. J. Comput. Syst. Sci. 54(1): 48-60 (1997) - [j111]Alfred V. Aho, David S. Johnson, Richard M. Karp, S. Rao Kosaraju, Catherine C. McGeoch, Christos H. Papadimitriou, Pavel A. Pevzner:
Emerging opportunities for theoretical computer science. SIGACT News 28(3): 65-74 (1997) - 1996
- [j110]Xiaotie Deng, Christos H. Papadimitriou:
Competitive Distributed Decision-Making. Algorithmica 16(2): 133-150 (1996) - [j109]Elias Koutsoupias, Christos H. Papadimitriou:
The 2-Evader Problem. Inf. Process. Lett. 57(5): 249-252 (1996) - [j108]Christos H. Papadimitriou, Mihalis Yannakakis:
On Limited Nondeterminism and the Complexity of the V-C Dimension. J. Comput. Syst. Sci. 53(2): 161-170 (1996) - [j107]Christos H. Papadimitriou, Martha Sideri:
The Bisection Width of Grid Graphs. Math. Syst. Theory 29(2): 97-110 (1996) - [j106]Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser:
The future of computational complexity theory: part I. SIGACT News 27(3): 6-12 (1996) - 1995
- [j105]Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan, Srihari Sampath Kumar:
Multimedia Information Caching for Personalized Video-on-Demand. Comput. Commun. 18(3): 204-216 (1995) - [j104]Elias Koutsoupias, Christos H. Papadimitriou:
On the k-Server Conjecture. J. ACM 42(5): 971-983 (1995) - [j103]Christos H. Papadimitriou:
Database metatheory: asking the big queries. SIGACT News 26(3): 13-30 (1995) - [j102]Pierluigi Crescenzi, Christos H. Papadimitriou:
Reversible Simulation of Space-Bounded Computations. Theor. Comput. Sci. 143(1): 159-165 (1995) - 1994
- [j101]Christos H. Papadimitriou, Martha Sideri:
Default Theories that Always Have Extensions. Artif. Intell. 69(1-2): 347-357 (1994) - [j100]Christos H. Papadimitriou, P. Venkat Rangan, Martha Sideri:
Designing Secure Communication Protocols from Trust Specification. Algorithmica 11(5): 485-499 (1994) - [j99]Christos H. Papadimitriou:
On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994) - [j98]Xiaotie Deng, Christos H. Papadimitriou:
On the Complexity of Cooperative Solution Concepts. Math. Oper. Res. 19(2): 257-266 (1994) - [j97]Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis:
The Complexity of Multiterminal Cuts. SIAM J. Comput. 23(4): 864-894 (1994) - 1993
- [j96]Christos H. Papadimitriou, Paolo Serafini, Mihalis Yannakakis:
Computing the Throughput of a Network with Dedicated Lines. Discret. Appl. Math. 42(2): 271-278 (1993) - [j95]Foto N. Afrati, Christos H. Papadimitriou:
The Parallel Complexity of Simple Logic Programs. J. ACM 40(4): 891-916 (1993) - [j94]Christos H. Papadimitriou, Mihalis Yannakakis:
The Traveling Salesman Problem with Distances One and Two. Math. Oper. Res. 18(1): 1-11 (1993) - 1992
- [j93]Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri:
On the Optimal Bisection of a Polygon. INFORMS J. Comput. 4(4): 435-438 (1992) - [j92]Elias Koutsoupias, Christos H. Papadimitriou:
On the Greedy Algorithm for Satisfiability. Inf. Process. Lett. 43(1): 53-55 (1992) - [j91]Christos H. Papadimitriou:
The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem. SIAM J. Comput. 21(3): 450-465 (1992) - 1991
- [j90]Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis:
On the Predictability of Coupled Automata: An Allegory about Chaos. Complex Syst. 5(5) (1991) - [j89]Joseph S. B. Mitchell, Christos H. Papadimitriou:
The Weighted Region Problem: Finding Shortest Paths Through a Weighted Planar Subdivision. J. ACM 38(1): 18-73 (1991) - [j88]Esther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis:
Modularity of Cycles and Paths in Graphs. J. ACM 38(2): 255-274 (1991) - [j87]Phokion G. Kolaitis, Christos H. Papadimitriou:
Why not Negation by Fixpoint? J. Comput. Syst. Sci. 43(1): 125-144 (1991) - [j86]Christos H. Papadimitriou, Mihalis Yannakakis:
Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci. 43(3): 425-440 (1991) - [j85]Xiaotie Deng, Christos H. Papadimitriou:
On path lengths modulo three. J. Graph Theory 15(3): 267-282 (1991) - [j84]Nimrod Megiddo, Christos H. Papadimitriou:
On Total Functions, Existence Theorems and Computational Complexity. Theor. Comput. Sci. 81(2): 317-324 (1991) - [j83]Christos H. Papadimitriou, Mihalis Yannakakis:
Shortest Paths Without a Map. Theor. Comput. Sci. 84(1): 127-150 (1991) - 1990
- [j82]Dimitris J. Kavvadias, Christos H. Papadimitriou:
A Linear Programming Approach to Reasoning about Probabilities. Ann. Math. Artif. Intell. 1: 189-205 (1990) - [j81]Christos H. Papadimitriou, Mihalis Yannakakis:
On recognizing integer polyhedra. Comb. 10(1): 107-109 (1990) - [j80]Xanthippi Markenscoff, Luqun Ni, Christos H. Papadimitriou:
The Geometry of Grasping. Int. J. Robotics Res. 9(1): 61-74 (1990) - [j79]John G. Kollias, Yannis Manolopoulos, Christos H. Papadimitriou:
The Optimum Execution Order of Queries in Linear Storage. Inf. Process. Lett. 36(3): 141-145 (1990) - [j78]Phokion G. Kolaitis, Christos H. Papadimitriou:
Some Computational Aspects of Circumscription. J. ACM 37(1): 1-14 (1990) - [j77]Christos H. Papadimitriou, Mihalis Yannakakis:
Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput. 19(2): 322-328 (1990) - 1989
- [j76]Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou:
Corrigendum: The Complexity of Cubical Graphs. Inf. Comput. 82(3): 350-353 (1989) - [j75]Xanthippi Markenscoff, Christos H. Papadimitriou:
Optimum Grip of a Polygon. Int. J. Robotics Res. 8(2): 17-29 (1989) - [j74]Ellen B. Feinberg, Christos H. Papadimitriou:
Finding Feasible Paths for a Two-Point Body. J. Algorithms 10(1): 109-119 (1989) - [j73]Michael D. Hirsch, Christos H. Papadimitriou, Stephen A. Vavasis:
Exponential lower bounds for finding Brouwer fix points. J. Complex. 5(4): 379-416 (1989) - [j72]Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman:
On the Convergence of Query Evaluation. J. Comput. Syst. Sci. 38(2): 341-359 (1989) - 1988
- [j71]Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou:
The Synthesis of Communication Protocols. Algorithmica 3: 451-472 (1988) - [j70]Sophocles Ephremidis, Christos H. Papadimitriou, Martha Sideri:
Complexity Characterizations of Attribute Grammar Languages. Inf. Comput. 78(3): 178-186 (1988) - [j69]David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis:
On Generating All Maximal Independent Sets. Inf. Process. Lett. 27(3): 119-123 (1988) - [j68]Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou:
The complexity of searching a graph. J. ACM 35(1): 18-44 (1988) - [j67]George F. Georgakopoulos, Dimitris J. Kavvadias, Christos H. Papadimitriou:
Probabilistic satisfiability. J. Complex. 4(1): 1-11 (1988) - [j66]Christos H. Papadimitriou, David Wolfe:
The Complexity of Facets Resolved. J. Comput. Syst. Sci. 37(1): 2-13 (1988) - [j65]Lefteris M. Kirousis, Christos H. Papadimitriou:
The Complexity of Recognizing Polyhedral Scenes. J. Comput. Syst. Sci. 37(1): 14-38 (1988) - [j64]David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis:
How Easy is Local Search? J. Comput. Syst. Sci. 37(1): 79-100 (1988) - 1987
- [j63]Christos H. Papadimitriou, Ellen B. Silverberg:
Optimal Piecewise Linear Motion of an Object Among Obstacles. Algorithmica 2: 523-539 (1987) - [j62]George K. Georgakopoulos, Christos H. Papadimitriou:
The 1-Steiner Tree Problem. J. Algorithms 8(1): 122-130 (1987) - [j61]Christos H. Papadimitriou, John N. Tsitsiklis:
The Complexity of Markov Decision Processes. Math. Oper. Res. 12(3): 441-450 (1987) - [j60]Christos H. Papadimitriou, John N. Tsitsiklis:
On Stochastic Scheduling with In-Tree Precedence Constraints. SIAM J. Comput. 16(1): 1-6 (1987) - [j59]Christos H. Papadimitriou, Mihalis Yannakakis:
The Complexity of Reliable Concurrency Control. SIAM J. Comput. 16(3): 538-553 (1987) - [j58]Christos H. Papadimitriou, Jeffrey D. Ullman:
A Communication-Time Tradeoff. SIAM J. Comput. 16(4): 639-646 (1987) - [j57]Joseph S. B. Mitchell, David M. Mount, Christos H. Papadimitriou:
The Discrete Geodesic Problem. SIAM J. Comput. 16(4): 647-668 (1987) - 1986
- [j56]Christos H. Papadimitriou, Mihalis Yannakakis:
A Note on Succinct Representations of Graphs. Inf. Control. 71(3): 181-185 (1986) - [j55]Foto N. Afrati, Stavros S. Cosmadakis, Christos H. Papadimitriou, George Papageorgiou, Nadia Papakostantinou:
The Complexity of the Travelling Repairman Problem. RAIRO Theor. Informatics Appl. 20(1): 79-87 (1986) - [j54]John N. Tsitsiklis, Christos H. Papadimitriou, Pierre A. Humblet:
The performance of a precedence-based queuing discipline. J. ACM 33(3): 593-602 (1986) - [j53]Esther M. Arkin, Christos H. Papadimitriou:
On the Complexity of Circulations. J. Algorithms 7(1): 134-145 (1986) - [j52]Thanasis Hadzilacos, Christos H. Papadimitriou:
Algorithmic Aspects of Multiversion Concurrency Control. J. Comput. Syst. Sci. 33(2): 297-310 (1986) - [j51]Lefteris M. Kirousis, Christos H. Papadimitriou:
Searching and Pebbling. Theor. Comput. Sci. 47(3): 205-218 (1986) - 1985
- [j50]Lefteris M. Kirousis, Christos H. Papadimitriou:
Interval graphs and seatching. Discret. Math. 55(2): 181-184 (1985) - [j49]Christos H. Papadimitriou:
A note the expressive power of Prolog. Bull. EATCS 26: 21-22 (1985) - [j48]Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou:
The Complexity of Cubical Graphs. Inf. Control. 66(1/2): 53-60 (1985) - [j47]Christos H. Papadimitriou:
An Algorithm for Shortest-Path Motion in Three Dimensions. Inf. Process. Lett. 20(5): 259-263 (1985) - [j46]Christos H. Papadimitriou:
Correction to "A Theorem in Database Concurrency Control". J. ACM 32(3): 750 (1985) - [j45]Christos H. Papadimitriou:
Games Against Nature. J. Comput. Syst. Sci. 31(2): 288-301 (1985) - [j44]Paris C. Kanellakis, Christos H. Papadimitriou:
The Complexity of Distributed Concurrency Control. SIAM J. Comput. 14(1): 52-74 (1985) - 1984
- [j43]Christos H. Papadimitriou:
On the complexity of unique solutions. J. ACM 31(2): 392-400 (1984) - [j42]Stavros S. Cosmadakis, Christos H. Papadimitriou:
Updates of Relational Views. J. ACM 31(4): 742-760 (1984) - [j41]Christos H. Papadimitriou, Umesh V. Vazirani:
On Two Geometric Problems Related to the Traveling Salesman Problem. J. Algorithms 5(2): 231-246 (1984) - [j40]Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou:
Inclusion Dependencies and Their Interaction with Functional Dependencies. J. Comput. Syst. Sci. 28(1): 29-59 (1984) - [j39]Paris C. Kanellakis, Christos H. Papadimitriou:
Is Distributed Locking Harder? J. Comput. Syst. Sci. 28(1): 103-120 (1984) - [j38]Christos H. Papadimitriou, Mihalis Yannakakis:
The Complexity of Facets (and Some Facets of Complexity). J. Comput. Syst. Sci. 28(2): 244-259 (1984) - [j37]Christos H. Papadimitriou, Michael Sipser:
Communication Complexity. J. Comput. Syst. Sci. 28(2): 260-269 (1984) - [j36]Andrea S. LaPaugh, Christos H. Papadimitriou:
The even-path problem for graphs and digraphs. Networks 14(4): 507-513 (1984) - [j35]Stavros S. Cosmadakis, Christos H. Papadimitriou:
The Traveling Salesman Problem with Many Visits to Few Cities. SIAM J. Comput. 13(1): 99-108 (1984) - [j34]Christos H. Papadimitriou, Paris C. Kanellakis:
On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9(1): 89-99 (1984) - 1983
- [j33]H. T. Kung, Christos H. Papadimitriou:
An Optimality Theory of Concurrency Control for Databases. Acta Informatica 19: 1-11 (1983) - [j32]Christos H. Papadimitriou:
Concurrency Control by Locking. SIAM J. Comput. 12(2): 215-226 (1983) - 1982
- [j31]Christos H. Papadimitriou, John N. Tsitsiklis:
On the Complexity of Designing Distributed Protocols. Inf. Control. 53(3): 211-218 (1982) - [j30]Christos H. Papadimitriou, Mihalis Yannakakis:
The complexity of restricted spanning tree problems. J. ACM 29(2): 285-309 (1982) - [j29]Christos H. Papadimitriou:
A theorem in database concurrency control. J. ACM 29(4): 998-1006 (1982) - [j28]Mihalis Yannakakis, Christos H. Papadimitriou:
Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41 (1982) - [j27]Richard M. Karp, Christos H. Papadimitriou:
On Linear Characterizations of Combinatorial Optimization Problems. SIAM J. Comput. 11(4): 620-632 (1982) - [j26]Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter:
Hamilton Paths in Grid Graphs. SIAM J. Comput. 11(4): 676-686 (1982) - [j25]Harry R. Lewis, Christos H. Papadimitriou:
Symmetric Space-Bounded Computation. Theor. Comput. Sci. 19: 161-187 (1982) - 1981
- [j24]Christos H. Papadimitriou, Mihalis Yannakakis:
On Minimal Eulerian Graphs. Inf. Process. Lett. 12(4): 203-205 (1981) - [j23]Christos H. Papadimitriou, Mihalis Yannakakis:
The Clique Problem for Planar Graphs. Inf. Process. Lett. 13(4/5): 131-133 (1981) - [j22]Manuel Blum, Richard M. Karp, Oliver Vornberger, Christos H. Papadimitriou, Mihalis Yannakakis:
The Complexity of Testing Whether a Graph is a Superconcentrator. Inf. Process. Lett. 13(4/5): 164-167 (1981) - [j21]Christos H. Papadimitriou:
On the complexity of integer programming. J. ACM 28(4): 765-768 (1981) - [j20]Witold Lipski Jr., Christos H. Papadimitriou:
A Fast Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems. J. Algorithms 2(3): 211-226 (1981) - [j19]Christos H. Papadimitriou:
Worst-Case and Probabilistic Analysis of a Geometric Location Problem. SIAM J. Comput. 10(3): 542-557 (1981) - [j18]Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael Rodeh:
Covering Graphs by Simple Circuits. SIAM J. Comput. 10(4): 746-750 (1981) - 1980
- [j17]Paris C. Kanellakis, Christos H. Papadimitriou:
Local Search for the Asymmetric Traveling Salesman Problem. Oper. Res. 28(5): 1086-1099 (1980) - [j16]Christos H. Papadimitriou, Paris C. Kanellakis:
Flowshop scheduling with limited temporary storage. J. ACM 27(3): 533-549 (1980) - [j15]M. R. Garey, David S. Johnson, Gerald L. Miller, Christos H. Papadimitriou:
The Complexity of Coloring Circular Arcs and Chords. SIAM J. Algebraic Discret. Methods 1(2): 216-227 (1980) - [j14]Christos H. Papadimitriou, Philip A. Bernstein:
On the Performance of Balanced Hashing Functions When the Keys Are Not Equiprobable. ACM Trans. Program. Lang. Syst. 2(1): 77-89 (1980) - 1979
- [j13]William H. Gates, Christos H. Papadimitriou:
Bounds for sorting by prefix reversal. Discret. Math. 27(1): 47-57 (1979) - [j12]Christos H. Papadimitriou:
Efficient Search for Rationals. Inf. Process. Lett. 8(1): 1-4 (1979) - [j11]Christos H. Papadimitriou:
Optimality of the Fast Fourier transform. J. ACM 26(1): 95-102 (1979) - [j10]Christos H. Papadimitriou:
The serializability of concurrent database updates. J. ACM 26(4): 631-653 (1979) - [j9]Christos H. Papadimitriou, Mihalis Yannakakis:
Scheduling Interval-Ordered Tasks. SIAM J. Comput. 8(3): 405-409 (1979) - 1978
- [j8]Christos H. Papadimitriou, Kenneth Steiglitz:
Some Examples of Difficult Traveling Salesman Problems. Oper. Res. 26(3): 434-443 (1978) - [j7]Christos H. Papadimitriou:
The adjacency relation on the traveling salesman polytope is NP-Complete. Math. Program. 14(1): 312-324 (1978) - [j6]Christos H. Papadimitriou:
The complexity of the capacitated tree problem. Networks 8(3): 217-230 (1978) - [j5]Philip A. Bernstein, James B. Rothnie Jr., Nathan Goodman, Christos H. Papadimitriou:
The Concurrency Control Mechanism of SDD-1: A System for Distributed Databases (The Fully Redundant Case). IEEE Trans. Software Eng. 4(3): 154-168 (1978) - 1977
- [j4]Christos H. Papadimitriou, Kenneth Steiglitz:
On the Complexity of Local Search for the Traveling Salesman Problem. SIAM J. Comput. 6(1): 76-83 (1977) - [j3]Christos H. Papadimitriou:
The Euclidean Traveling Salesman Problem is NP-Complete. Theor. Comput. Sci. 4(3): 237-244 (1977) - 1976
- [j2]Christos H. Papadimitriou:
The NP-Completeness of the bandwidth minimization problem. Computing 16(3): 263-270 (1976) - [j1]Christos H. Papadimitriou:
On the complexity of edge traversing. J. ACM 23(3): 544-554 (1976)
Conference and Workshop Papers
- 2024
- [c243]Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala:
Computation with Sequences of Assemblies in a Model of the Brain. ALT 2024: 499-504 - [c242]Binghui Peng, Christos H. Papadimitriou:
The complexity of non-stationary reinforcement learning. ALT 2024: 972-996 - [c241]William Brown, Christos H. Papadimitriou, Tim Roughgarden:
Online Stackelberg Optimization via Nonlinear Control. COLT 2024: 697-749 - [c240]Rashida Hakim, Jason Milionis, Christos H. Papadimitriou, Georgios Piliouras:
Swim till You Sink: Computing the Limit of a Game. SAGT 2024: 205-222 - 2023
- [c239]Amol Pasarkar, Christos H. Papadimitriou, Mihalis Yannakakis:
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. ITCS 2023: 88:1-88:20 - [c238]Christos H. Papadimitriou, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Manolis Zampetakis:
The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points. EC 2023: 1045 - 2022
- [c237]Francesco D'Amore, Daniel Mitropolsky, Pierluigi Crescenzi, Emanuele Natale, Christos H. Papadimitriou:
Planning with Biological Neurons and Synapses. AAAI 2022: 21-28 - [c236]Max Dabagia, Santosh S. Vempala, Christos H. Papadimitriou:
Assemblies of neurons learn to classify well-separated distributions. COLT 2022: 3685-3717 - [c235]Xi Chen, Christos H. Papadimitriou, Binghui Peng:
Memory Bounds for Continual Learning. FOCS 2022: 519-530 - [c234]Christos H. Papadimitriou, Denis Turcu:
Optimal Scheduling of the Leaves of a Tree and the SVO Frequencies of Languages. LION 2022: 3-14 - 2021
- [c233]Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, Karthik Narasimhan:
Self-Attention Networks Can Process Bounded Hierarchical Languages. ACL/IJCNLP (1) 2021: 3770-3785 - [c232]Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, Christos H. Papadimitriou:
Total Functions in the Polynomial Hierarchy. ITCS 2021: 44:1-44:18 - [c231]Ronald Fagin, Georg Gottlob, Christos H. Papadimitriou, Moshe Y. Vardi, Giorgio Ausiello, Maurizio Lenzerini, Domenico Saccà, Luigi Palopoli, Francesco Scarcello:
Panel on "Past and Future of Computer Science Theory" (Discussion Paper). SEBD 2021: 531-542 - [c230]Christos H. Papadimitriou, Binghui Peng:
Public Goods Games in Directed Networks. EC 2021: 745-762 - [c229]Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc:
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. EC 2021: 763-764 - [c228]Christos Harilaos Papadimitriou, Kiran Vodrahalli, Mihalis Yannakakis:
The Platform Design Problem. WINE 2021: 317-333 - 2020
- [c227]Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis:
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. ITCS 2020: 18:1-18:19 - 2019
- [c226]Xi Chen, Christos H. Papadimitriou, Tim Roughgarden:
An Axiomatic Approach to Block Rewards. AFT 2019: 124-131 - [c225]Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Christos H. Papadimitriou:
Energy Equilibria in Proof-of-Work Mining. EC 2019: 489-502 - [c224]Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin:
Optimal Strategies of Blotto Games: Beyond Convexity. EC 2019: 597-616 - [c223]Christos H. Papadimitriou, Santosh S. Vempala:
Random Projection in the Brain and Computation with Assemblies of Neurons. ITCS 2019: 57:1-57:19 - [c222]Kurtulus Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, Georgios Piliouras:
Wealth Inequality and the Price of Anarchy. STACS 2019: 31:1-31:16 - 2018
- [c221]Christos H. Papadimitriou:
About Place Cells and Grid Cells - About Place Cells and Grid Cells. Adventures Between Lower Bounds and Higher Altitudes 2018: 637-640 - [c220]Paul W. Goldberg, Christos H. Papadimitriou:
Towards a Unified Complexity Theory of Total Functions. ITCS 2018: 37:1-37:20 - [c219]Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, Santosh S. Vempala:
Long Term Memory and the Densest K-Subgraph Problem. ITCS 2018: 57:1-57:15 - [c218]Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos H. Papadimitriou, Amin Saberi, Santosh S. Vempala:
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons. NeurIPS 2018: 10880-10890 - [c217]Maximilian Haas-Heger, Christos H. Papadimitriou, Mihalis Yannakakis, Garud Iyengar, Matei T. Ciocarlie:
Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis. Robotics: Science and Systems 2018 - [c216]Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark:
From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games. SODA 2018: 2291-2310 - [c215]Panayotis Mertikopoulos, Christos H. Papadimitriou, Georgios Piliouras:
Cycles in Adversarial Regularized Learning. SODA 2018: 2703-2717 - 2017
- [c214]Paul W. Goldberg, Christos H. Papadimitriou:
TFNP: An Update. CIAC 2017: 3-9 - [c213]Eleni Bakali, Panagiotis Cheilaris, Dimitris Fotakis, Martin Fürer, Costas D. Koutras, Euripides Markou, Christos Nomikos, Aris Pagourtzis, Christos H. Papadimitriou, Nikolaos S. Papaspyrou, Katerina Potika:
Stathis Zachos at 70! CIAC 2017: 469-484 - 2016
- [c212]Christos H. Papadimitriou, Samantha Petti, Santosh S. Vempala:
Cortical Computation via Iterative Constructions. COLT 2016: 1357-1375 - [c211]Christos H. Papadimitriou:
Understanding evolution through algorithms. FMCAD 2016: 2 - [c210]Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein:
Can Almost Everybody be Almost Happy? ITCS 2016: 1-9 - [c209]Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, Mary Wootters:
Strategic Classification. ITCS 2016: 111-122 - [c208]Christos H. Papadimitriou, Georgios Piliouras:
From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology. ITCS 2016: 227-235 - [c207]Christos H. Papadimitriou, Nisheeth K. Vishnoi:
On the Computational Complexity of Limit Cycles in Dynamical Systems. ITCS 2016: 403 - [c206]Cathy Wu, Kalyanaraman Shankari, Ece Kamar, Randy H. Katz, David E. Culler, Christos H. Papadimitriou, Eric Horvitz, Alexandre M. Bayen:
Optimizing the diamond lane: A more tractable carpool problem and algorithms. ITSC 2016: 1389-1396 - [c205]Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, Jan Arne Telle:
On Satisfiability Problems with a Linear Structure. IPEC 2016: 14:1-14:14 - [c204]Robert Legenstein, Christos H. Papadimitriou, Santosh S. Vempala, Wolfgang Maass:
Variable Binding through Assemblies in Spiking Neural Networks. CoCo@NIPS 2016 - [c203]Constantinos Daskalakis, Christos H. Papadimitriou, Christos Tzamos:
Does Information Revelation Improve Revenue? EC 2016: 233-250 - [c202]Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer:
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. SODA 2016: 414-429 - [c201]Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein:
On the Complexity of Dynamic Mechanism Design. SODA 2016: 1458-1475 - [c200]Christos H. Papadimitriou:
Computation as a Scientific Weltanschauung (Invited Talk). SWAT 2016: 33:1-33:1 - [c199]Xiaotie Deng, Zhe Feng, Christos H. Papadimitriou:
Power-Law Distributions in a Two-Sided Market and Net Neutrality. WINE 2016: 59-72 - 2015
- [c198]Christos H. Papadimitriou:
On Neural Networks and Paul Spirakis. Algorithms, Probability, Networks, and Games 2015: 27-28 - [c197]Yang Cai, Constantinos Daskalakis, Christos H. Papadimitriou:
Optimum Statistical Estimation with Strategic Data Sources. COLT 2015: 280-296 - [c196]Christos H. Papadimitriou, Santosh S. Vempala:
Cortical Learning via Prediction. COLT 2015: 1402-1422 - [c195]Christos H. Papadimitriou, Santosh S. Vempala:
Cortical Computation. PODC 2015: 1-2 - [c194]Georgios Kouroupas, Evangelos Markakis, Christos H. Papadimitriou, Vasileios Rigas, Martha Sideri:
The Web Graph as an Equilibrium. SAGT 2015: 203-215 - 2014
- [c193]Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan:
Satisfiability and Evolution. FOCS 2014: 524-530 - [c192]Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:
Algorithms, Games, and Evolution (Invited Talk). FSTTCS 2014: 45-46 - [c191]Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein:
On Simplex Pivoting Rules and Complexity Theory. IPCO 2014: 13-24 - [c190]Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein:
The complexity of fairness through equilibrium. EC 2014: 209-226 - [c189]Yang Cai, Christos H. Papadimitriou:
Simultaneous bayesian auctions and computational complexity. EC 2014: 895-910 - 2013
- [c188]Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:
Multiplicative updates in coordination games and the theory of evolution. ITCS 2013: 57-58 - [c187]Azza Abouzied, Dana Angluin, Christos H. Papadimitriou, Joseph M. Hellerstein, Avi Silberschatz:
Learning and verifying quantified boolean queries by example. PODS 2013: 49-60 - 2012
- [c186]Christos H. Papadimitriou, Leonard M. Adleman, Richard M. Karp, Donald E. Knuth, Robert E. Tarjan, Leslie G. Valiant:
An Algorithmic View of the Universe. ACM-TURING 2012: 13:1 - [c185]Ilias Diakonikolas, Christos H. Papadimitriou, George Pierrakos, Yaron Singer:
Efficiency-Revenue Trade-Offs in Auctions. ICALP (2) 2012: 488-499 - [c184]Christos H. Papadimitriou:
The New Faces of Combinatorial Optimization. ISCO 2012: 19-23 - 2011
- [c183]Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani:
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. FOCS 2011: 67-76 - [c182]Christos H. Papadimitriou, Christopher A. Wilkens:
Economies with non-convex production and complexity equilibria. EC 2011: 137-146 - [c181]Shahar Dobzinski, Christos H. Papadimitriou, Yaron Singer:
Mechanisms for complement-free procurement. EC 2011: 273-282 - [c180]Constantinos Daskalakis, Christos H. Papadimitriou:
Continuous Local Search. SODA 2011: 790-804 - [c179]Christos H. Papadimitriou, George Pierrakos:
On optimal single-item auctions. STOC 2011: 119-128 - [c178]Ilias Foudalis, Kamal Jain, Christos H. Papadimitriou, Martha Sideri:
Modeling Social Networks through User Background and Behavior. WAW 2011: 85-102 - [c177]Christos H. Papadimitriou:
Games, algorithms, and the Internet. WWW 2011: 5-6 - 2010
- [c176]Christos H. Papadimitriou, Gregory Valiant:
A New Look at Selfish Routing. ICS 2010: 178-187 - [c175]Amos Fiat, Christos H. Papadimitriou:
When the Players Are Not Expectation Maximizers. SAGT 2010: 1-14 - [c174]Constantinos Daskalakis, Rafael M. Frongillo, Christos H. Papadimitriou, George Pierrakos, Gregory Valiant:
On Learning Algorithms for Nash Equilibria. SAGT 2010: 114-125 - [c173]David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans:
Inapproximability for VCG-Based Combinatorial Auctions. SODA 2010: 518-536 - 2009
- [c172]Christos H. Papadimitriou:
Algorithmic Game Theory: A Snapshot. ICALP (1) 2009: 3-11 - [c171]Constantinos Daskalakis, Christos H. Papadimitriou:
On a Network Generalization of the Minmax Theorem. ICALP (2) 2009: 423-434 - [c170]Catriel Beeri, Phokion G. Kolaitis, Christos H. Papadimitriou:
The ACM PODS Alberto O. Mendelzon test-of-time-award 2009. PODS 2009: 43 - [c169]Constantinos Daskalakis, Christos H. Papadimitriou:
On oblivious PTAS's for nash equilibrium. STOC 2009: 75-84 - [c168]Ilan Adler, Constantinos Daskalakis, Christos H. Papadimitriou:
A Note on Strictly Competitive Games. WINE 2009: 471-474 - 2008
- [c167]Constantinos Daskalakis, Christos H. Papadimitriou:
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. FOCS 2008: 25-34 - [c166]Christos H. Papadimitriou, Michael Schapira, Yaron Singer:
On the Hardness of Being Truthful. FOCS 2008: 250-259 - [c165]Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno:
On the Complexity of Reconfiguration Problems. ISAAC 2008: 28-39 - [c164]Christos H. Papadimitriou:
The Search for Equilibrium Concepts. SAGT 2008: 1-3 - [c163]Alex Fabrikant, Christos H. Papadimitriou:
The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. SODA 2008: 844-853 - [c162]Henry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou:
Linked decompositions of networks and the power of choice in Polya urns. SODA 2008: 993-1002 - [c161]Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou:
The myth of the folk theorem. STOC 2008: 365-372 - [c160]Christos H. Papadimitriou:
Some Recent Results in Algorithmic Game Theory. WINE 2008: 17 - 2007
- [c159]Christos H. Papadimitriou:
Nash Equilibria: Where We Stand. ESA 2007: 1 - [c158]Constantinos Daskalakis, Christos H. Papadimitriou:
Computing Equilibria in Anonymous Games. FOCS 2007: 83-93 - [c157]Lucian Popa, Afshin Rostamizadeh, Richard M. Karp, Christos H. Papadimitriou, Ion Stoica:
Balancing traffic load in wireless networks with curveball routing. MobiHoc 2007: 170-179 - [c156]Moshe Babaioff, Robert Kleinberg, Christos H. Papadimitriou:
Congestion games with malicious players. EC 2007: 103-112 - [c155]Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou:
Progress in approximate nash equilibria. EC 2007: 355-358 - [c154]Christos H. Papadimitriou:
The Computation of Equilibria. WINE 2007: 5-6 - [c153]Alexander Hall, Evdokia Nikolova, Christos H. Papadimitriou:
Incentive-Compatible Interdomain Routing with Linear Utilities. WINE 2007: 232-244 - 2006
- [c152]Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. ICALP (1) 2006: 346-357 - [c151]Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou:
The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. ICALP (1) 2006: 513-524 - [c150]Constantinos Daskalakis, Christos H. Papadimitriou:
Computing pure nash equilibria in graphical games via markov random fields. EC 2006: 91-99 - [c149]Paul W. Goldberg, Christos H. Papadimitriou:
Reducibility among equilibrium problems. STOC 2006: 61-70 - [c148]Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
The complexity of computing a Nash equilibrium. STOC 2006: 71-78 - [c147]Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou:
A Note on Approximate Nash Equilibria. WINE 2006: 297-306 - 2005
- [c146]Alexander Hall, Christos H. Papadimitriou:
Approximating the Distortion. APPROX-RANDOM 2005: 111-122 - [c145]Christos H. Papadimitriou:
Games Other People Play. CONCUR 2005: 5 - [c144]Christos H. Papadimitriou:
Algorithmic Problems in Ad Hoc Networks. DCOSS 2005: 1 - [c143]Konstantinos Daskalakis, Christos H. Papadimitriou:
The Complexity of Games on Highly Regular Graphs. ESA 2005: 71-82 - [c142]Vladlen Koltun, Christos H. Papadimitriou:
Approximately Dominating Representatives. ICDT 2005: 204-214 - [c141]Christos H. Papadimitriou, Tim Roughgarden:
Computing equilibria in multi-player games. SODA 2005: 82-91 - [c140]Christos H. Papadimitriou, Shmuel Safra:
The complexity of low-distortion embeddings between point sets. SODA 2005: 112-118 - [c139]Christos H. Papadimitriou:
Computing correlated equilibria in multi-player games. STOC 2005: 49-56 - [c138]Christos H. Papadimitriou:
... The Interaction Between Algorithms and Game Theory. WEA 2005: 1-3 - [c137]Christos H. Papadimitriou:
Recent Developments in Equilibria Algorithms. WINE 2005: 1-2 - [c136]Georgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri:
Experiments with an Economic Model of the Worldwide Web. WINE 2005: 46-54 - [c135]Georgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri:
An economic model of the worldwide web. WWW (Special interest tracks and posters) 2005: 934-935 - 2004
- [c134]Christos H. Papadimitriou, David Ratajczak:
On a Conjecture Related to Geometric Routing. ALGOSENSORS 2004: 9-17 - [c133]Christos H. Papadimitriou:
Networks and Games. HiPC 2004: 7 - [c132]Jeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker:
Global Synchronization in Sensornets. LATIN 2004: 609-624 - [c131]Byung-Gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos H. Papadimitriou, John Kubiatowicz:
Selfish caching in distributed systems: a game-theoretic analysis. PODC 2004: 21-30 - [c130]Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar:
The complexity of pure Nash equilibria. STOC 2004: 604-612 - 2003
- [c129]Christos H. Papadimitriou:
The New Problems. PCK50 2003: 10 - [c128]Christos H. Papadimitriou:
Games and Networks. FCT 2003: 157 - [c127]Milena Mihail, Christos H. Papadimitriou, Amin Saberi:
On Certain Connectivity Properties of the Internet Topology. FOCS 2003: 28-35 - [c126]Christos H. Papadimitriou:
Mythematics: storytelling in the teaching of computer science and mathematics. ITiCSE 2003: 1 - [c125]Ananth Rao, Christos H. Papadimitriou, Scott Shenker, Ion Stoica:
Geographic routing without location information. MobiCom 2003: 96-108 - [c124]Alex Fabrikant, Ankur Luthra, Elitza N. Maneva, Christos H. Papadimitriou, Scott Shenker:
On a network creation game. PODC 2003: 347-351 - [c123]Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos:
An approximate truthful mechanism for combinatorial auctions with single parameter agents. SODA 2003: 205-214 - 2002
- [c122]Christos H. Papadimitriou:
Learning the Internet. COLT 2002: 396 - [c121]Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani:
Market Equilibrium via a Primal-Dual-Type Algorithm. FOCS 2002: 389-395 - [c120]Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou:
Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. ICALP 2002: 110-122 - [c119]Christos H. Papadimitriou:
The Internet, the Web, and Algorithms. LATIN 2002: 2 - [c118]Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker:
A BGP-based mechanism for lowest-cost routing. PODC 2002: 173-182 - [c117]Milena Mihail, Christos H. Papadimitriou:
On the Eigenvalue Power Law. RANDOM 2002: 254-262 - [c116]Christos H. Papadimitriou:
Understanding the Internet. SETN 2002: 1-2 - [c115]Aditya Akella, Srinivasan Seshan, Richard M. Karp, Scott Shenker, Christos H. Papadimitriou:
Selfish behavior and stability of the internet: a game-theoretic analysis of TCP. SIGCOMM 2002: 117-130 - [c114]Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra:
On the complexity of equilibria. STOC 2002: 67-71 - [c113]Christos H. Papadimitriou:
The Joy of Theory. STOC 2002: 116 - 2001
- [c112]Christos H. Papadimitriou:
Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. FOCS 2001: 4-8 - [c111]Christos H. Papadimitriou:
Algorithmic problems related to the Internet. HERCMA 2001: 92 - [c110]Christos H. Papadimitriou:
Algorithms, Games, and the Internet. ICALP 2001: 1-3 - [c109]Christos H. Papadimitriou, Mihalis Yannakakis:
Multiobjective Query Optimization. PODS 2001 - [c108]Christos H. Papadimitriou:
Game theory, algorithms, and the Internet. SODA 2001: 391 - [c107]Christos H. Papadimitriou:
Algorithms, games, and the internet. STOC 2001: 749-753 - 2000
- [c106]Christos H. Papadimitriou:
Theoretical Problems Related to the Internet. COCOON 2000: 1-2 - [c105]Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker:
Optimization Problems in Congestion Control. FOCS 2000: 66-74 - [c104]Christos H. Papadimitriou, Mihalis Yannakakis:
On the Approximability of Trade-offs and Optimal Access of Web Sources. FOCS 2000: 86-92 - [c103]Christos H. Papadimitriou:
On certain rigorous approaches to data mining (invited talk, abstract only). KDD 2000: 2 - [c102]Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
Auditing Boolean Attributes. PODS 2000: 86-91 - [c101]Christos H. Papadimitriou, Santosh S. Vempala:
On the approximability of the traveling salesman problem (extended abstract). STOC 2000: 126-133 - [c100]Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker:
Sharing the cost of muliticast transmissions (preliminary version). STOC 2000: 218-227 - 1999
- [c99]Gene Cheung, Steven McCanne, Christos H. Papadimitriou:
Software Synthesis of Variable-length Code Decoder Using a Mixture of Programmed Logic and Table Lookups. Data Compression Conference 1999: 121-130 - [c98]Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou:
Algorithmic Aspects of Protein Structure Similarity. FOCS 1999: 512-522 - [c97]Christos H. Papadimitriou:
Novel Computational Approaches to Information Retrieval and Data Mining (Abstract). ICDT 1999: 31 - [c96]Georg Gottlob, Christos H. Papadimitriou:
On the Complexity of Single-Rule Datalog Queries. LPAR 1999: 201-222 - [c95]Christos H. Papadimitriou:
Topological Queries. SSD 1999: 3-4 - [c94]Elias Koutsoupias, Christos H. Papadimitriou:
Worst-case Equilibria. STACS 1999: 404-413 - 1998
- [c93]Christos H. Papadimitriou:
Algorithmic Approaches to Information Retrieval and Data Mining (Abstract). COCOON 1998: 1 - [c92]Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh S. Vempala:
Latent Semantic Indexing: A Probabilistic Analysis. PODS 1998: 159-168 - [c91]Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis:
On the complexity of protein folding (abstract). RECOMB 1998: 61-62 - [c90]Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
Segmentation Problems. STOC 1998: 473-482 - [c89]Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou:
Planar Map Graphs. STOC 1998: 514-523 - [c88]Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis:
On the Complexity of Protein Folding (Extended Abstract). STOC 1998: 597-603 - 1997
- [c87]Christos H. Papadimitriou:
Planar Topological Queries. CDB 1997: 1-6 - [c86]Christos H. Papadimitriou:
NP-Completeness: A Retrospective. ICALP 1997: 2-6 - [c85]Xiaotie Deng, Christos H. Papadimitriou:
Decision-Making by Hierarchies of Discordant Agents. ISAAC 1997: 183-192 - [c84]Christos H. Papadimitriou, Mihalis Yannakakis:
On the Complexity of Database Queries. PODS 1997: 12-19 - [c83]Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou:
On the Analysis of Indexing Schemes. PODS 1997: 249-256 - [c82]Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou:
Panarity, Revisited (Extended Abstract). WADS 1997: 472-473 - 1996
- [c81]Christos H. Papadimitriou:
The Complexity of Knowledge Representation. CCC 1996: 244-248 - [c80]Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou:
On the Difficulty of Designing Good Classifiers. COCOON 1996: 273-279 - [c79]Christos H. Papadimitriou:
Computational Aspacts of Organization Theory (Extended Abstract). ESA 1996: 559-564 - [c78]Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis:
Searching a Fixed Graph. ICALP 1996: 280-289 - [c77]Serge Abiteboul, Gabriel M. Kuper, Christos H. Papadimitriou, Moshe Y. Vardi:
In Memoriam: Paris C. Kanellakis. PODS 1996: 79 - [c76]Christos H. Papadimitriou, Dan Suciu, Victor Vianu:
Topological Queries in Spatial Databases. PODS 1996: 81-92 - 1995
- [c75]Michelangelo Grigni, Elias Koutsoupias, Christos H. Papadimitriou:
An Approximation Scheme for Planar Graph TSP. FOCS 1995: 640-645 - [c74]Goran Gogic, Henry A. Kautz, Christos H. Papadimitriou, Bart Selman:
The Comparative Linguistics of Knowledge Representation. IJCAI (1) 1995: 862-869 - [c73]Michelangelo Grigni, Dimitris Papadias, Christos H. Papadimitriou:
Topological Inference. IJCAI (1) 1995: 901-907 - [c72]Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan:
Optimal Information Delivery. ISAAC 1995: 181-187 - [c71]Christos H. Papadimitriou:
Database Metatheory: Asking the Big Queries. PODS 1995: 1-10 - 1994
- [c70]Goran Gogic, Christos H. Papadimitriou, Martha Sideri:
Incremental Recompilation of Knowledge. AAAI 1994: 922-927 - [c69]Milena Mihail, Christos H. Papadimitriou:
On the Random Walk Method for Protocol Testing. CAV 1994: 132-141 - [c68]Christos H. Papadimitriou, John N. Tsitsiklis:
The Complexity of Optimal Queueing Network Control. SCT 1994: 318-322 - [c67]Elias Koutsoupias, Christos H. Papadimitriou:
Beyond Competitive Analysis. FOCS 1994: 394-400 - [c66]Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki:
Motion Planning on a Graph (Extended Abstract). FOCS 1994: 511-520 - [c65]Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan:
Information Caching for Delivery of Personalized Video Programs on Home Entertainment Channels. ICMCS 1994: 214-223 - [c64]Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu:
The Power of Reflective Relational Machines. LICS 1994: 230-240 - [c63]Christos H. Papadimitriou, Mihalis Yannakakis:
On complexity as bounded rationality (extended abstract). STOC 1994: 726-733 - 1993
- [c62]Christos H. Papadimitriou, Mihalis Yannakakis:
On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract). SCT 1993: 12-18 - [c61]Dimitris J. Kavvadias, Christos H. Papadimitriou, Martha Sideri:
On Horn Envelopes and Hypergraph Transversals. ISAAC 1993: 399-405 - [c60]Christos H. Papadimitriou, Mihalis Yannakakis:
Linear programming without the matrix. STOC 1993: 121-129 - 1992
- [c59]Christos H. Papadimitriou, Martha Sideri:
On Finding Extensions of Default Theories. ICDT 1992: 276-281 - [c58]Xiaotie Deng, Christos H. Papadimitriou:
Competitive Distributed Decision-Making. IFIP Congress (1) 1992: 350-356 - [c57]Christos H. Papadimitriou, Mihalis Yannakakis:
Tie-Breaking Semantics and Structural Totality. PODS 1992: 16-22 - [c56]Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis:
The Complexity of Multiway Cuts (Extended Abstract). STOC 1992: 241-251 - 1991
- [c55]Christos H. Papadimitriou:
On Selecting a Satisfying Truth Assignment (Extended Abstract). FOCS 1991: 163-169 - [c54]Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou:
How to Learn an Unknown Environment (Extended Abstract). FOCS 1991: 298-303 - [c53]Christos H. Papadimitriou, P. Venkat Rangan, Martha Sideri:
Designing Secure Communication Protocols from Trust Specifications. FSTTCS 1991: 360-368 - [c52]Christos H. Papadimitriou:
Decision-Making with Incomplete Information. ISA 1991: 1 - [c51]Christos H. Papadimitriou, Mihalis Yannakakis:
On the Value of Information in Distributed Decision-Making (Extended Abstract). PODC 1991: 61-64 - [c50]Christos H. Papadimitriou, Martha Sideri:
Optimal Coteries. PODC 1991: 75-80 - 1990
- [c49]Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri:
On the Optimal Bisection of a Polygon (Extended Abstract). SCG 1990: 198-202 - [c48]Xiaotie Deng, Christos H. Papadimitriou:
Exploring an Unknown Graph (Extended Abstract). FOCS 1990: 355-361 - [c47]Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis:
On the Predictability of Coupled Automata: An Allegory about Chaos. FOCS 1990: 788-793 - [c46]Christos H. Papadimitriou:
On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract). FOCS 1990: 794-801 - [c45]Christos H. Papadimitriou, Martha Sideri:
The Bisection Width of Grid Graphs. SODA 1990: 405-410 - [c44]Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis:
On the Complexity of Local Search (Extended Abstract). STOC 1990: 438-445 - 1989
- [c43]Christos H. Papadimitriou, Mihalis Yannakakis:
Shortest Paths Without a Map. ICALP 1989: 610-620 - 1988
- [c42]Phokion G. Kolaitis, Christos H. Papadimitriou:
Some Computational Aspects of Circumscription. AAAI 1988: 455-469 - [c41]Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou:
Scheduling Dags to Minimize Time and Communication. AWOC 1988: 134-138 - [c40]Phokion G. Kolaitis, Christos H. Papadimitriou:
Why Not Negation by Fixpoint? PODS 1988: 231-239 - [c39]Christos H. Papadimitriou, Mihalis Yannakakis:
Optimization, Approximation, and Complexity Classes (Extended Abstract). STOC 1988: 229-234 - [c38]Christos H. Papadimitriou, Mihalis Yannakakis:
Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract). STOC 1988: 510-513 - 1987
- [c37]Sophocles Ephremidis, Christos H. Papadimitriou, Martha Sideri:
Complexity characterizations of attribute grammar languages. SCT 1987: 10-13 - [c36]Joseph S. B. Mitchell, Christos H. Papadimitriou:
The Weighted Region Problem. SCG 1987: 30-38 - [c35]Foto N. Afrati, Christos H. Papadimitriou:
The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213 - 1986
- [c34]Christos H. Papadimitriou:
Shortest-Path Motion. FSTTCS 1986: 144-153 - [c33]Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou:
The Synthesis of Communication Protocols. PODC 1986: 263-271 - [c32]Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman:
Convergence of Sideways Query Evaluation. PODS 1986: 24-30 - 1985
- [c31]David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis:
How Easy Is Local Search? (Extended Abstract). FOCS 1985: 39-42 - [c30]Christos H. Papadimitriou, David Wolfe:
The Complexity of Facets Resolved. FOCS 1985: 74-78 - [c29]Lefteris M. Kirousis, Christos H. Papadimitriou:
The Complexity of Recognizing Polyhedral Scenes (Extended Abstract). FOCS 1985: 175-185 - [c28]Thanasis Hadzilacos, Christos H. Papadimitriou:
Algorithmic Aspects of Multiversion Concurrency Control. PODS 1985: 96-104 - [c27]Christos H. Papadimitriou, Mihalis Yannakakis:
The Complexity of Reliable Concurrency Control. PODS 1985: 230-234 - 1984
- [c26]Christos H. Papadimitriou, Jeffrey D. Ullman:
A Communication-Time Tradeoff. FOCS 1984: 84-88 - [c25]Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou:
The Complexity of Cubical Graphs (Extended Abstract). ICALP 1984: 51-57 - 1983
- [c24]Fillia Makedon, Christos H. Papadimitriou, Ivan Hal Sudborough:
Topological Bandwidth. CAAP 1983: 317-331 - [c23]Christos H. Papadimitriou:
Games Against Nature (Extended Abstract). FOCS 1983: 446-450 - [c22]Mihalis Yannakakis, Paris C. Kanellakis, Stavros S. Cosmadakis, Christos H. Papadimitriou:
Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract). ICALP 1983: 712-722 - [c21]Stavros S. Cosmadakis, Christos H. Papadimitriou:
Updates of Relational Views. PODS 1983: 317-331 - [c20]Christos H. Papadimitriou:
Theory of concurrency control. Theoretical Computer Science 1983: 35-47 - [c19]Christos H. Papadimitriou, Stathis Zachos:
Two remarks on the power of counting. Theoretical Computer Science 1983: 269-276 - 1982
- [c18]Christos H. Papadimitriou:
On the Complexity of Unique Solutions. FOCS 1982: 14-20 - [c17]Christos H. Papadimitriou, Paris C. Kanellakis:
On Concurrency Control by Multiple Versions. PODS 1982: 76-82 - [c16]Paris C. Kanellakis, Christos H. Papadimitriou:
Is Distributed Locking Harder? PODS 1982: 98-107 - [c15]Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou:
Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176 - [c14]Christos H. Papadimitriou, Michael Sipser:
Communication Complexity. STOC 1982: 196-200 - [c13]Christos H. Papadimitriou, Mihalis Yannakakis:
The Complexity of Facets (and Some Facets of Complexity). STOC 1982: 255-260 - 1981
- [c12]Paris C. Kanellakis, Christos H. Papadimitriou:
The Complexity of Distributed Concurrency Control. FOCS 1981: 185-197 - [c11]Christos H. Papadimitriou, Mihalis Yannakakis:
Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract). FOCS 1981: 358-363 - [c10]Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou:
The Complexity of Searching a Graph (Preliminary Version). FOCS 1981: 376-385 - [c9]Christos H. Papadimitriou:
On the Power of Locking. SIGMOD Conference 1981: 148-154 - 1980
- [c8]Richard M. Karp, Christos H. Papadimitriou:
On Linear Characterizations of Combinatorial Optimization Problems. FOCS 1980: 1-9 - [c7]Mihalis Yannakakis, Christos H. Papadimitriou:
Algebraic Dependencies (Extended Abstract). FOCS 1980: 328-332 - [c6]Harry R. Lewis, Christos H. Papadimitriou:
Symmetric Space-Bounded Computation (Extended Abstract). ICALP 1980: 374-384 - [c5]Christos H. Papadimitriou, Jon Louis Bentley:
A Worst-Case Analysis of Nearest Neighbor Searching by Projection. ICALP 1980: 470-482 - 1979
- [c4]Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung:
Locking Policies: Safety and Freedom from Deadlock. FOCS 1979: 286-297 - [c3]Christos H. Papadimitriou, Mihalis Yannakakis:
The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). ICALP 1979: 460-470 - [c2]H. T. Kung, Christos H. Papadimitriou:
An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 - 1976
- [c1]Christos H. Papadimitriou, Kenneth Steiglitz:
Some Complexity Results for the Traveling Salesman Problem. STOC 1976: 1-9
Parts in Books or Collections
- 2023
- [p2]Christos H. Papadimitriou:
Cook's NP-completeness Paper and the Dawn of the New Theory. Logic, Automata, and Computational Complexity 2023: 73-82 - 2019
- [p1]Wolfgang Maass, Christos H. Papadimitriou, Santosh S. Vempala, Robert Legenstein:
Brain Computation: A Computer Science Perspective. Computing and Software Science 2019: 184-199
Editorship
- 2017
- [e4]Christos H. Papadimitriou:
8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA. LIPIcs 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-029-3 [contents] - 2008
- [e3]Christos H. Papadimitriou, Shuzhong Zhang:
Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings. Lecture Notes in Computer Science 5385, Springer 2008, ISBN 978-3-540-92184-4 [contents] - 1999
- [e2]Victor Vianu, Christos H. Papadimitriou:
Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, USA. ACM Press 1999, ISBN 1-58113-062-7 [contents] - 1983
- [e1]David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, Joel I. Seiferas:
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA. ACM 1983 [contents]
Informal and Other Publications
- 2024
- [i65]Binghui Peng, Srini Narayanan, Christos H. Papadimitriou:
On Limitations of the Transformer Architecture. CoRR abs/2402.08164 (2024) - [i64]Christos H. Papadimitriou, Giorgos Filandrianos, Maria Lymperaiou, Giorgos Stamou:
Masked Generative Story Transformer with Character Guidance and Caption Augmentation. CoRR abs/2403.08502 (2024) - [i63]Max Dabagia, Daniel Mitropolsky, Christos H. Papadimitriou, Santosh S. Vempala:
Coin-Flipping In The Brain: Statistical Learning with Neuronal Assemblies. CoRR abs/2406.07715 (2024) - [i62]William Brown, Christos H. Papadimitriou, Tim Roughgarden:
Online Stackelberg Optimization via Nonlinear Control. CoRR abs/2406.18805 (2024) - [i61]Rashida Hakim, Ana-Andreea Stoica, Christos H. Papadimitriou, Mihalis Yannakakis:
The Fairness-Quality Trade-off in Clustering. CoRR abs/2408.10002 (2024) - [i60]Rashida Hakim, Jason Milionis, Christos H. Papadimitriou, Georgios Piliouras:
Swim till You Sink: Computing the Limit of a Game. CoRR abs/2408.11146 (2024) - 2023
- [i59]Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala:
Computation with Sequences in the Brain. CoRR abs/2306.03812 (2023) - [i58]Daniel Mitropolsky, Christos H. Papadimitriou:
The Architecture of a Biologically Plausible Language Organ. CoRR abs/2306.15364 (2023) - [i57]Christos H. Papadimitriou, Binghui Peng:
The complexity of non-stationary reinforcement learning. CoRR abs/2307.06877 (2023) - 2022
- [i56]Jason Milionis, Christos H. Papadimitriou, Georgios Piliouras, Kelly Spendlove:
Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics. CoRR abs/2203.14129 (2022) - [i55]Xi Chen, Christos H. Papadimitriou, Binghui Peng:
Memory Bounds for Continual Learning. CoRR abs/2204.10830 (2022) - [i54]Daniel Mitropolsky, Adiba Ejaz, Mirah Shi, Mihalis Yannakakis, Christos H. Papadimitriou:
Center-Embedding and Constituency in the Brain and a New Characterization of Context-Free Languages. CoRR abs/2206.13217 (2022) - [i53]Christos H. Papadimitriou, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Manolis Zampetakis:
The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points. CoRR abs/2207.07557 (2022) - [i52]Amol Pasarkar, Mihalis Yannakakis, Christos H. Papadimitriou:
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP. CoRR abs/2209.07625 (2022) - 2021
- [i51]Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc:
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. CoRR abs/2102.10261 (2021) - [i50]Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, Karthik Narasimhan:
Self-Attention Networks Can Process Bounded Hierarchical Languages. CoRR abs/2105.11115 (2021) - [i49]Christos H. Papadimitriou, Binghui Peng:
Public Good Games in Directed Networks. CoRR abs/2106.00718 (2021) - [i48]Daniel Mitropolsky, Michael J. Collins, Christos H. Papadimitriou:
A Biologically Plausible Parser. CoRR abs/2108.02189 (2021) - [i47]Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala:
Assemblies of neurons can learn to classify well-separated distributions. CoRR abs/2110.03171 (2021) - [i46]Francesco D'Amore, Daniel Mitropolsky, Pierluigi Crescenzi, Emanuele Natale, Christos H. Papadimitriou:
Planning with Biological Neurons and Synapses. CoRR abs/2112.08186 (2021) - 2020
- [i45]Polina Golland, Jack L. Gallant, Greg Hager, Hanspeter Pfister, Christos H. Papadimitriou, Stefan Schaal, Joshua T. Vogelstein:
A New Age of Computing and the Brain. CoRR abs/2004.12926 (2020) - [i44]Christos H. Papadimitriou, Kiran Vodrahalli, Mihalis Yannakakis:
The Platform Design Problem. CoRR abs/2009.06117 (2020) - [i43]Robert Kleinberg, Daniel Mitropolsky, Christos H. Papadimitriou:
Total Functions in the Polynomial Hierarchy. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [i42]Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin:
Optimal Strategies of Blotto Games: Beyond Convexity. CoRR abs/1901.04153 (2019) - [i41]Shayegan Omidshafiei, Christos H. Papadimitriou, Georgios Piliouras, Karl Tuyls, Mark Rowland, Jean-Baptiste Lespiau, Wojciech M. Czarnecki, Marc Lanctot, Julien Pérolat, Rémi Munos:
α-Rank: Multi-Agent Evaluation by Evolution. CoRR abs/1903.01373 (2019) - [i40]Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis:
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. CoRR abs/1909.03210 (2019) - [i39]Xi Chen, Christos H. Papadimitriou, Tim Roughgarden:
An Axiomatic Approach to Block Rewards. CoRR abs/1909.10645 (2019) - 2018
- [i38]Kurtulus Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, Georgios Piliouras:
Wealth Inequality and the Price of Anarchy. CoRR abs/1802.09269 (2018) - [i37]Maximilian Haas-Heger, Christos H. Papadimitriou, Mihalis Yannakakis, Garud Iyengar, Matei T. Ciocarlie:
Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis. CoRR abs/1806.01384 (2018) - [i36]Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos H. Papadimitriou, Amin Saberi, Santosh S. Vempala:
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons. CoRR abs/1810.11896 (2018) - 2017
- [i35]Panayotis Mertikopoulos, Christos H. Papadimitriou, Georgios Piliouras:
Cycles in adversarial regularized learning. CoRR abs/1709.02738 (2017) - [i34]Paul W. Goldberg, Christos H. Papadimitriou:
Towards a Unified Complexity Theory of Total Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i33]Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, Jan Arne Telle:
On Satisfiability Problems with a Linear Structure. CoRR abs/1602.07876 (2016) - [i32]Christos H. Papadimitriou, Samantha Petti, Santosh S. Vempala:
Cortical Computation via Iterative Constructions. CoRR abs/1602.08357 (2016) - [i31]Christos H. Papadimitriou:
On the optimality of grid cells. CoRR abs/1606.04876 (2016) - [i30]Xiaotie Deng, Zhe Feng, Christos H. Papadimitriou:
Power-Law Distributions in a Two-sided Market and Net Neutrality. CoRR abs/1610.04809 (2016) - 2015
- [i29]Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein:
Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash. CoRR abs/1504.02411 (2015) - [i28]Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, Mary Wootters:
Strategic Classification. CoRR abs/1506.06980 (2015) - [i27]Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer:
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. CoRR abs/1507.02351 (2015) - [i26]Christos H. Papadimitriou, Nisheeth K. Vishnoi:
On the Computational Complexity of Limit Cycles in Dynamical Systems. CoRR abs/1511.07605 (2015) - 2014
- [i25]Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein:
On Simplex Pivoting Rules and Complexity Theory. CoRR abs/1404.3320 (2014) - [i24]Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein:
The Intractability of Dynamic Mechanism Design. CoRR abs/1407.5373 (2014) - [i23]Yang Cai, Constantinos Daskalakis, Christos H. Papadimitriou:
Optimum Statistical Estimation with Strategic Data Sources. CoRR abs/1408.2539 (2014) - [i22]Christos H. Papadimitriou, Santosh S. Vempala:
Unsupervised Learning through Prediction in a Model of Cortex. CoRR abs/1412.7955 (2014) - 2013
- [i21]Azza Abouzied, Dana Angluin, Christos H. Papadimitriou, Joseph M. Hellerstein, Avi Silberschatz:
Learning and Verifying Quantified Boolean Queries by Example. CoRR abs/1304.4303 (2013) - [i20]Constantinos Daskalakis, Christos H. Papadimitriou:
Sparse Covers for Sums of Indicators. CoRR abs/1306.1265 (2013) - [i19]Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Andrew Wan:
Satisfiability and Evolution. CoRR abs/1312.1983 (2013) - [i18]Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein:
The Complexity of Fairness through Equilibrium. CoRR abs/1312.6249 (2013) - 2012
- [i17]Ilias Diakonikolas, Christos H. Papadimitriou, George Pierrakos, Yaron Singer:
Efficiency-Revenue Trade-offs in Auctions. CoRR abs/1205.3077 (2012) - [i16]Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:
Multiplicative Updates in Coordination Games and the Theory of Evolution. CoRR abs/1208.3160 (2012) - 2011
- [i15]Constantinos Daskalakis, Christos H. Papadimitriou:
On Oblivious PTAS's for Nash Equilibrium. CoRR abs/1102.2280 (2011) - 2010
- [i14]Christos H. Papadimitriou, Yaron Singer:
Budget Feasible Mechanisms. CoRR abs/1002.2334 (2010) - [i13]Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani:
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. CoRR abs/1006.5352 (2010) - [i12]Christos H. Papadimitriou, George Pierrakos:
On Optimal Single-Item Auctions. CoRR abs/1011.1279 (2010) - 2009
- [i11]Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer:
VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension. CoRR abs/0905.1995 (2009) - 2008
- [i10]Constantinos Daskalakis, Christos H. Papadimitriou:
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. CoRR abs/0808.2801 (2008) - 2007
- [i9]Constantinos Daskalakis, Christos H. Papadimitriou:
Computing Equilibria in Anonymous Games. CoRR abs/0710.5582 (2007) - [i8]Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou:
The Myth of the Folk Theorem. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [i7]Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. CoRR abs/cs/0609072 (2006) - [i6]Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [i5]Paul W. Goldberg, Christos H. Papadimitriou:
Reducibility Among Equilibrium Problems. Electron. Colloquium Comput. Complex. TR05 (2005) - [i4]Konstantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
The complexity of computing a Nash equilibrium. Electron. Colloquium Comput. Complex. TR05 (2005) - [i3]Konstantinos Daskalakis, Christos H. Papadimitriou:
Three-Player Games Are Hard. Electron. Colloquium Comput. Complex. TR05 (2005) - 1999
- [i2]Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou:
Map Graphs. CoRR cs.DM/9910013 (1999) - 1998
- [i1]Goran Gogic, Christos H. Papadimitriou, Martha Sideri:
Incremental Recompilation of Knowledge. CoRR cs.AI/9801101 (1998)
Coauthor Index
Constantinos Daskalakis
aka: Konstantinos Daskalakis
aka: Konstantinos Daskalakis
[j163] [j124] [j115] [j112] [j108] [j97] [j96] [j94] [j88] [j86] [j83] [j81] [j77] [j69] [j64] [j59] [j56] [j38] [j30] [j28] [j24] [j23] [j22] [j9] [c239] [c228] [c227] [c217] [c109] [c104] [c91] [c88] [c84] [c78] [c63] [c62] [c60] [c57] [c56] [c51] [c44] [c43] [c39] [c38] [c31] [c27] [c22] [c13] [c11] [c7] [c4] [c3] [i61] [i54] [i52] [i44] [i40] [i37]
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:09 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
