Edit Profile (opens in new tab) Papadimitriou, Christos Harilaos Compute Distance To: Compute Author ID: papadimitriou.christos-h Published as: Papadimitriou, Christos H.; Papadimitriou, Christos; Papadimitriou, C. H.; Paradimitriou, Christos H.; Papadimtriou, Christos; Papadimitriou, Ch. H. more...less External Links: MGP · Wikidata · dblp · GND · IdRef Documents Indexed: 278 Publications since 1976, including 9 Books 5 Contributions as Editor Biographic References: 2 Publications Co-Authors: 212 Co-Authors with 237 Joint Publications 5,412 Co-Co-Authors all top 5 Co-Authors 46 single-authored 31 Yannakakis, Mihalis 16 Sideri, Martha 13 Daskalakis, Constantinos 13 Koutsoupias, Elias 11 Deng, Xiao-Tie 9 Tsitsiklis, John N. 7 Afrati, Foto N. 7 Goldberg, Paul W. 7 Johnson, David Stifler 7 Rubinstein, Aviad 6 Grigni, Michelangelo 6 Kanellakis, Paris Christos 6 Papageorgiou, George 6 Pierrakos, George 6 Shenker, Scott J. 6 Steiglitz, Kenneth 5 Fabrikant, Alex 5 Raghavan, Prabhakar 5 Vempala, Santosh S. 4 Chen, Zhizhong 4 Cosmadakis, Stavros S. 4 Crescenzi, Pierluigi 4 Feigenbaum, Joan 4 Karp, Richard Manning 4 Kleinberg, Jon Michael 4 Kolaitis, Phokion G. 3 Arkin, Esther M. 3 Kirousis, Lefteris Miltiades 3 Lewis, Harry R. 3 Livnat, Adi 3 Maneva, Elitza N. 3 Megiddo, Nimrod 3 Mitchell, Joseph S. B. 3 Piliouras, Georgios 3 Safra, Muli 3 Singer, Yaron 3 Talwar, Kunal 2 Adler, Ilan 2 Archer, Aaron F. 2 Baaz, Matthias 2 Bernstein, Philip A. 2 Borgs, Christian 2 Chayes, Jennifer Tour 2 Demaine, Erik D. 2 Doxiadis, Apostolos 2 Garey, Michael Randolph 2 Georgakopoulos, George F. 2 Gopalan, Parikshit 2 Gottlob, Georg 2 Hall, Alexander 2 Harper, Charles L. jun. 2 Harvey, Nicholas J. A. 2 Immorlica, Nicole 2 Itai, Alon 2 Ito, Takehiro 2 Kalai, Adam Tauman 2 Kavvadias, Dimitris J. 2 Kleinberg, Robert D. 2 Koltun, Vladlen 2 Makedon, F. S. 2 Mihail, Milena 2 Mirrokni, Vahab S. 2 Mount, David M. 2 Psomas, Christos-Alexandros 2 Putnam, Hilary Whitehall 2 Ratajczak, David 2 Roughgarden, Tim 2 Saberi, Amin 2 Sami, Rahul 2 Scott, Dana Stewart 2 Sudborough, Ivan Hal 2 Tardos, Éva 2 Uehara, Ryuhei 2 Ullman, Jeffrey David 2 Uno, Yushi 2 Vazirani, Umesh V. 2 Vianu, Victor 1 Abiteboul, Serge 1 Amanatidis, Christos 1 Babaioff, Moshe 1 Babichenko, Yakov 1 Badanidiyuru, Ashwinkumar 1 Bakali, Eleni 1 Ban, Frank 1 Barreno, Marco 1 Behnezhad, Soheil 1 Bentley, Jon Louis 1 Blondel, Vincent D. 1 Blum, Avrim L. 1 Blum, Manuel 1 Bournez, Olivier 1 Buchfuhrer, Dave 1 Buss, Samuel R. 1 Cai, Yang 1 Candogan, Ozan 1 Casanova, Marco Antonio 1 Chastain, Erick 1 Chaudhuri, Kamalika 1 Cheilaris, Panagiotis 1 Chun, Byung-Gon ...and 115 more Co-Authors all top 5 Serials 25 Journal of Computer and System Sciences 20 SIAM Journal on Computing 15 Journal of the Association for Computing Machinery 12 Theoretical Computer Science 9 Information Processing Letters 6 Journal of the ACM 5 Mathematics of Operations Research 5 Journal of Algorithms 5 Algorithmica 5 Games and Economic Behavior 4 Information and Computation 3 Information and Control 3 Networks 2 Discrete Mathematics 2 Journal of Graph Theory 2 Operations Research 2 Bulletin of the Greek Mathematical Society 2 SIAM Journal on Algebraic and Discrete Methods 2 Operations Research Letters 2 Combinatorica 2 Journal of Complexity 2 Proceedings of the National Academy of Sciences of the United States of America 2 Annals of Mathematics and Artificial Intelligence 2 Internet Mathematics 1 Acta Informatica 1 Artificial Intelligence 1 Discrete Applied Mathematics 1 ACM Transactions on Database Systems 1 Computing 1 Journal of Economic Theory 1 Kiberneticheskiĭ Sbornik. Novaya Seriya 1 Mathematical Programming 1 Mathematical Systems Theory 1 Naval Research Logistics 1 SIAM Journal on Control and Optimization 1 Theoretical Population Biology 1 ACM Transactions on Programming Languages and Systems 1 Systems & Control Letters 1 The Journal of Logic Programming 1 Probability Theory and Related Fields 1 Complex Systems 1 Neural Computation 1 ORSA Journal on Computing 1 Distributed Computing 1 RAIRO. Informatique Théorique et Applications 1 Mathematical Programming. Series A. Series B 1 The Journal of Artificial Intelligence Research (JAIR) 1 Journal of Combinatorial Optimization 1 RIMS Kokyuroku 1 Bulletin Société Mathématique de Grèce. Nouvelle Série 1 Lecture Notes in Computer Science 1 LIPIcs – Leibniz International Proceedings in Informatics 1 Journal of Theoretical Biology 1 Computer Science Review all top 5 Fields 246 Computer science (68-XX) 69 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 58 Operations research, mathematical programming (90-XX) 44 Combinatorics (05-XX) 19 Mathematical logic and foundations (03-XX) 9 General and overarching topics; collections (00-XX) 8 Numerical analysis (65-XX) 7 History and biography (01-XX) 6 Information and communication theory, circuits (94-XX) 5 Biology and other natural sciences (92-XX) 3 Probability theory and stochastic processes (60-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Geometry (51-XX) 2 Systems theory; control (93-XX) 1 Number theory (11-XX) 1 Group theory and generalizations (20-XX) 1 Operator theory (47-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Convex and discrete geometry (52-XX) 1 General topology (54-XX) 1 Algebraic topology (55-XX) 1 Statistics (62-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 242 Publications have been cited 9,207 times in 7,311 Documents Cited by ▼ Year ▼ Computational complexity. Zbl 0833.68049Papadimitriou, Christos H. 850 1994 Combinatorial optimization: algorithms and complexity. Zbl 0503.90060Papadimitriou, Christos H.; Steiglitz, Kenneth 744 1982 Optimization, approximation, and complexity classes. Zbl 0765.68036Papadimitriou, Christos H.; Yannakakis, Mihalis 436 1991 Computational complexity. Zbl 0557.68033Papadimitriou, C. H. 422 1985 Worst-case equilibria. Zbl 1099.91501Koutsoupias, Elias; Papadimitriou, Christos 362 1999 Combinatorial optimization: algorithms and complexity. Corr. repr. of the 1982 original. Zbl 0944.90066Papadimitriou, Christos H.; Steiglitz, Kenneth 232 1998 The complexity of multiterminal cuts. Zbl 0809.68075Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. 205 1994 On generating all maximal independent sets. Zbl 0654.68086Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H. 182 1988 On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048Papadimitriou, Christos H. 159 1994 Algorithms, games, and the internet. Zbl 1323.68022Papadimitriou, Christos 153 2001 How easy is local search? Zbl 0655.68074Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis 150 1988 The complexity of computing a Nash equilibrium. Zbl 1185.91019Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H. 144 2009 The complexity of pure Nash equilibria. Zbl 1192.91042Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal 134 2004 Hamilton paths in grid graphs. Zbl 0506.05043Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz 126 1982 Worst-case equilibria. Zbl 1303.91012Koutsoupias, Elias; Papadimitriou, Christos 122 2009 The complexity of searching a graph. Zbl 0637.68081Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H. 110 1988 The Euclidean traveling salesman problem is NP-complete. Zbl 0386.90057Papadimitriou, Christos H. 109 1977 The complexity of facets (and some facets of complexity). Zbl 0571.68028Papadimitriou, C. H.; Yannakakis, M. 108 1984 On the complexity of cooperative solution concepts. Zbl 0824.90146Deng, Xiaotie; Papadimitriou, Christos H. 107 1994 Searching and pebbling. Zbl 0616.68064Kirousis, Lefteris M.; Papadimitriou, Christos H. 105 1986 The NP-completeness of the bandwidth minimization problem. Zbl 0321.65019Papadimitriou, Ch. H. 105 1976 The complexity of coloring circular arcs and chords. Zbl 0499.05058Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H. 102 1980 The traveling salesman problem with distances one and two. Zbl 0778.90057Papadimitriou, Christos H.; Yannakakis, Mihalis 97 1993 On the complexity of reconfiguration problems. Zbl 1207.68166Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi 93 2011 Shortest paths without a map. Zbl 0733.68065Papadimitriou, Christos H.; Yannakakis, Mihalis 88 1991 On a network creation game. Zbl 1322.91013Fabrikant, Alex; Luthra, Ankur; Maneva, Elitza; Papadimitriou, Christos H.; Shenker, Scott 82 2003 On the complexity of integer programming. Zbl 0468.68050Papadimitriou, Christos H. 81 1981 Elements of the theory of computation. Zbl 0464.68001Lewis, Harry R.; Papadimitriou, Christos H. 77 1981 The discrete geodesic problem. Zbl 0625.68051Mitchell, Joseph S. B.; Mount, David M.; Papadimitriou, Christos H. 76 1987 The complexity of Markov decision processes. Zbl 0638.90099Papadimitriou, Christos H.; Tsitsiklis, John N. 75 1987 The serializability of concurrent database updates. Zbl 0419.68036Papadimitriou, Christos H. 73 1979 The complexity of computing a Nash equilibrium. Zbl 1301.68142Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H. 72 2006 Bounds for sorting by prefix reversal. Zbl 0397.68062Gates, William H.; Papadimitriou, Christos H. 70 1979 Scheduling interval-ordered tasks. Zbl 0421.68040Papadimitriou, C. H.; Yannakakis, M. 60 1979 On total functions, existence theorems and computational complexity. Zbl 0731.68036Megiddo, Nimrod; Papadimitriou, Christos H. 58 1991 The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03024Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza; Papadimitriou, Christos H. 57 2009 Inverval scheduling: a survey. Zbl 1143.90337Kolen, Antoon W. J.; Lenstra, Jan Karel; Papadimitriou, Christos H.; Spieksma, Frits C. R. 56 2007 On the \(k\)-server conjecture. Zbl 0885.68075Koutsoupias, Elias; Papadimitriou, Christos H. 56 1995 The complexity of facets resolved. Zbl 0655.68041Papadimitriou, Christos H.; Wolfe, David 55 1988 Probabilistic satisfiability. Zbl 0647.68049Georgakopoulos, George; Kavvadias, Dimitris; Papadimitriou, Christos H. 53 1988 The complexity of restricted spanning tree problems. Zbl 0478.68068Papadimitriou, Christos H.; Yannakakis, Mihalis 52 1982 Flowshop scheduling with limited temporary storage. Zbl 0475.68014Papadimitriou, Christos H.; Kanellakis, Paris C. 51 1980 Interval graphs and searching. Zbl 0566.05056Kirousis, Lefteris M.; Papadimitriou, Christos H. 51 1985 The weighted region problem: Finding shortest paths through a weighted planar subdivision. Zbl 0799.68150Mitchell, Joseph S. B.; Papadimitriou, Christos H. 49 1991 The complexity of the travelling repairman problem. Zbl 0585.68057Afrati, Foto; Cosmadakis, Stavros; Papadimitriou, Christos H.; Papageorgiou, George; Papakostantinou, Nadia 46 1986 Latent semantic indexing: A probabilistic analysis. Zbl 0963.68063Papadimitriou, Christos H.; Raghavan, Prabhakar; Tamaki, Hisao; Vempala, Santosh 46 2000 A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe 43 2002 Computing correlated equilibria in multi-player games. Zbl 1314.91012Papadimitriou, Christos H.; Roughgarden, Tim 43 2008 Symmetric space-bounded computation. Zbl 0491.68045Lewis, Harry R.; Papadimitriou, Christos H. 42 1982 Exploring an unknown graph. Zbl 0941.68099Deng, Xiaotie; Papadimitriou, Christos H. 42 1999 Sharing the cost of multicast transmissions. Zbl 0996.68026Feigenbaum, Joan; Papadimitriou, Christos H.; Shenker, Scott 42 2001 Games against nature. Zbl 0583.68020Papadimitriou, Christos H. 41 1985 On two geometric problems related to the travelling salesman problem. Zbl 0551.90093Papadimitriou, Christos H.; Vazirani, Umesh V. 40 1984 On limited nondeterminism and the complexity of the V-C dimension. Zbl 0859.68031Papadimitriou, Christos H.; Yannakakis, Mihalis 40 1996 How to learn an unknown environment. I: The rectilinear case. Zbl 0904.68115Deng, Xiaotie; Kameda, Tiko; Papadimitriou, Christos 39 1998 The complexity of optimal queuing network control. Zbl 0977.90008Papadimitriou, Christos H.; Tsitsiklis, John N. 39 1999 Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V. 38 2008 Topological bandwidth. Zbl 0573.05052Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H. 38 1985 On a conjecture related to geometric routing. Zbl 1079.68078Papadimitriou, Christos H.; Ratajczak, David 38 2005 Beyond competitive analysis. Zbl 0959.68131Koutsoupias, Elias; Papadimitriou, Christos H. 37 2000 A note on approximate Nash equilibria. Zbl 1167.91390Daskalakis, Constantinos; Mehta, Aranyak; Papadimitriou, Christos 36 2009 Worst-case and probabilistic analysis of a geometric location problem. Zbl 0461.68078Papadimitriou, Christos H. 34 1981 Towards an architecture-independent analysis of parallel algorithms. Zbl 0692.68032Papadimitriou, Christos H.; Yannakakis, Mihalis 34 1990 The adjacency relation on the traveling salesman polytope is NP-complete. Zbl 0376.90067Papadimitriou, Christos H. 33 1978 On the complexity of edge traversing. Zbl 0351.90079Papadimitriou, Christos H. 32 1976 Communication complexity. Zbl 0584.68064Papadimitriou, Christos H.; Sipser, Michael 31 1984 Map graphs. Zbl 1323.05039Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. 31 2002 The theory of database concurrency control. Zbl 0609.68073Papadimitriou, Christos 30 1986 On linear characterizations of combinatorial optimization problems. Zbl 0505.65020Karp, Richard M.; Papadimitriou, Christos H. 29 1982 An algorithm for shortest-path motion in three dimensions. Zbl 0603.68070Papadimitriou, Christos H. 29 1985 Inclusion dependencies and their interaction with functional dependencies. Zbl 0586.68082Casanova, Marco A.; Fagin, Ronald; Papadimitriou, Christos H. 28 1984 On the complexity of database queries. Zbl 0939.68024Papadimitriou, Christos H.; Yannakakis, Mihalis 27 1999 Exponential lower bounds for finding Brouwer fixed points. Zbl 0696.65045Hirsch, Michael D.; Papadimitriou, Christos H.; Vavasis, Stephen A. 27 1989 The complexity of the capacitated tree problem. Zbl 0443.68048Papadimitriou, C. H. 26 1978 Some examples of difficult traveling salesman problems. Zbl 0383.90105Papadimitriou, C. H.; Steiglitz, K. 26 1978 Why not negation by fixpoint? Zbl 0753.68028Kolaitis, Phokion G.; Papadimitriou, Christos H. 26 1991 A note on succinct representations of graphs. Zbl 0616.68041Papadimitriou, Christos H.; Yannakakis, Mihalis 25 1986 Searching a fixed graph. Zbl 1045.90532Koutsoupias, Elias; Papadimitriou, Christos; Yannakakis, Mihalis 25 1996 Continuous local search. Zbl 1373.68263Daskalakis, Constantinos; Papadimitriou, Christos 25 2011 On Horn envelopes and hypergraph transversals. (Extended abstract). Zbl 0925.03036Kavvdias, Dimitris; Papadimitriou, Christos; Sideri, Martha 24 1993 A linear programming approach to reasoning about probabilities. Zbl 0878.68034Kavvadias, Dimitris; Papadimitriou, Christos H. 24 1990 Covering graphs by simple circuits. Zbl 0468.68071Itai, Alon; Lipton, Richard J.; Papadimitriou, Christos H.; Rodeh, M. 22 1981 An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1094.68528Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva 22 2003 Local search for the asymmetric traveling salesman problem. Zbl 0447.90082Kanellakis, Paris-C.; Papadimitriou, Christos H. 21 1980 Deciding stability and mortality of piecewise affine dynamical systems. Zbl 0973.68067Blondel, V. D.; Bournez, O.; Koiran, P.; Papadimitriou, C. H.; Tsitsiklis, J. N. 21 2001 Approximate Nash equilibria in anonymous games. Zbl 1330.91015Daskalakis, Constantinos; Papadimitriou, Christos H. 21 2015 Planar map graphs. Zbl 1028.68104Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. 20 1998 On oblivious PTAS’s for Nash equilibrium. Zbl 1304.91014Daskalakis, Constantinos; Papadimitriou, Christos H. 20 2009 On complexity as bounded rationality (extended abstract). Zbl 1345.68216Papadimitriou, Christos H.; Yannakakis, Mihalis 19 1994 Algorithms, games, and the internet (extended abstract). Zbl 0986.68566Papadimitriou, Christos H. 19 2001 On the complexity of protein folding (extended abstract). Zbl 1007.68511Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis 19 1998 Computing equilibria in multi-player games. Zbl 1297.91005Papadimitriou, Christos H.; Roughgarden, Tim 19 2005 The even-path problem for graphs and digraphs. Zbl 0552.68059LaPaugh, Andrea S.; Papadimitriou, Christos H. 18 1984 Performance guarantees for heuristics. Zbl 0574.90086Johnson, D. S.; Papadimitriou, C. H. 18 1985 Efficient search for rationals. Zbl 0411.65037Papadimitriou, Christos H. 18 1979 Reducibility among equilibrium problems. Zbl 1301.68161Goldberg, Paul W.; Papadimitriou, Christos H. 18 2006 Approximately dominating representatives. Zbl 1108.68042Koltun, Vladlen; Papadimitriou, Christos H. 18 2007 Segmentation problems. Zbl 1317.90329Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar 17 2004 Computing correlated equilibria in multi-player games. Zbl 1192.91021Papadimitriou, Christos H. 17 2005 On the approximability of the traveling salesman problem. Zbl 1106.90071Papadimitriou, Christos H.; Vempala, Santosh 17 2006 Reductions in PPP. Zbl 1446.68067Ban, Frank; Jain, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad 1 2019 Random projection in the brain and computation with assemblies of neurons. Zbl 07559100Papadimitriou, Christos H.; Vempala, Santosh S. 1 2019 Wealth inequality and the price of anarchy. Zbl 07559140Gemici, Kurtuluş; Koutsoupias, Elias; Monnot, Barnabé; Papadimitriou, Christos H.; Piliouras, Georgios 1 2019 Towards a unified complexity theory of total functions. Zbl 1393.68053Goldberg, Paul W.; Papadimitriou, Christos H. 11 2018 Cycles in adversarial regularized learning. Zbl 1403.68200Mertikopoulos, Panayotis; Papadimitriou, Christos; Piliouras, Georgios 10 2018 Long term memory and the densest K-subgraph problem. Zbl 1462.68041Legenstein, Robert; Maass, Wolfgang; Papadimitriou, Christos H.; Vempala, Santosh S. 2 2018 From battlefields to elections: winning strategies of Blotto and auditing games. Zbl 1403.91013Behnezhad, Soheil; Blum, Avrim; Derakhshan, Mahsa; HajiAghayi, Mohammad Taghi; Mahdian, Mohammad; Papadimitriou, Christos H.; Rivest, Ronald L.; Seddighin, Saeed; Stark, Philip B. 1 2018 On satisfiability problems with a linear structure. Zbl 1398.68235Gaspers, Serge; Papadimitriou, Christos H.; Sæther, Sigve Hortemo; Telle, Jan Arne 4 2017 TFNP: an update. Zbl 1486.68080Goldberg, Paul W.; Papadimitriou, Christos H. 2 2017 Stathis Zachos at 70! Zbl 1486.68007Bakali, Eleni; Cheilaris, Panagiotis; Fotakis, Dimitris; Fürer, Martin; Koutras, Costas D.; Markou, Euripides; Nomikos, Christos; Pagourtzis, Aris; Papadimitriou, Christos H.; Papaspyrou, Nikolaos S.; Potika, Katerina 1 2017 Zero-sum polymatrix games: a generalization of minmax. Zbl 1336.91009Cai, Yang; Candogan, Ozan; Daskalakis, Constantinos; Papadimitriou, Christos 8 2016 Locally adaptive optimization: adaptive seeding for monotone submodular functions. Zbl 1423.90157Badanidiyuru, Ashwinkumar; Papadimitriou, Christos; Rubinstein, Aviad; Seeman, Lior; Singer, Yaron 4 2016 Can almost everybody be almost happy? Zbl 1335.91021Babichenko, Yakov; Papadimitriou, Christos; Rubinstein, Aviad 4 2016 On the complexity of dynamic mechanism design. Zbl 1417.91247Papadimitriou, Christos; Pierrakos, George; Psomas, Christos-Alexandros; Rubinstein, Aviad 3 2016 From Nash equilibria to chain recurrent sets: solution concepts and topology. Zbl 1335.91009Papadimitriou, Christos; Piliouras, Georgios 3 2016 Strategic classification. Zbl 1334.68184Hardt, Moritz; Megiddo, Nimrod; Papadimitriou, Christos; Wootters, Mary 1 2016 Approximate Nash equilibria in anonymous games. Zbl 1330.91015Daskalakis, Constantinos; Papadimitriou, Christos H. 21 2015 Sparse covers for sums of indicators. Zbl 1334.60048Daskalakis, Constantinos; Papadimitriou, Christos 5 2015 Optimal deterministic auctions with correlated priors. Zbl 1318.91102Papadimitriou, Christos; Pierrakos, George 2 2015 The web graph as an equilibrium. Zbl 1358.68030Kouroupas, Georgios; Markakis, Evangelos; Papadimitriou, Christos; Rigas, Vasileios; Sideri, Martha 1 2015 Algorithms, games, and evolution. Zbl 1355.91017Chastain, Erick; Livnat, Adi; Papadimitriou, Christos; Vazirani, Umesh 16 2014 On simplex pivoting rules and complexity theory. Zbl 1418.90145Adler, Ilan; Papadimitriou, Christos; Rubinstein, Aviad 7 2014 Efficiency-revenue trade-offs in auctions. Zbl 1367.91077Diakonikolas, Ilias; Papadimitriou, Christos; Pierrakos, George; Singer, Yaron 7 2012 On the complexity of reconfiguration problems. Zbl 1207.68166Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi 93 2011 Continuous local search. Zbl 1373.68263Daskalakis, Constantinos; Papadimitriou, Christos 25 2011 On optimal single-item auctions. Zbl 1288.90087Papadimitriou, Christos H.; Pierrakos, George 10 2011 Modeling social networks through user background and behavior. Zbl 1328.91262Foudalis, Ilias; Jain, Kamal; Papadimitriou, Christos; Sideri, Martha 4 2011 The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions. Zbl 1292.91013Goldberg, Paul W.; Papadimitriou, Christos H.; Savani, Rahul 3 2011 Kurt Gödel and the foundations of mathematics. Horizons of truth. Zbl 1253.00009 1 2011 An analytical contrast between fitness maximization and selection for mixability. Zbl 1405.92197Livnat, Adi; Papadimitriou, Christos; M. W. Feldman, Marcus W. 1 2011 When the players are not expectation maximizers. Zbl 1253.91009Fiat, Amos; Papadimitriou, Christos 12 2010 Inapproximability for VCG-based combinatorial auctions. Zbl 1288.91099Buchfuhrer, Dave; Dughmi, Shaddin; Fu, Hu; Kleinberg, Robert; Mossel, Elchanan; Papadimitriou, Christos; Schapira, Michael; Singer, Yaron; Umans, Chris 10 2010 The myth of the folk theorem. Zbl 1207.91012Borgs, Christian; Chayes, Jennifer; Immorlica, Nicole; Kalai, Adam Tauman; Mirrokni, Vahab; Papadimitriou, Christos 7 2010 On learning algorithms for Nash equilibria. Zbl 1310.91033Daskalakis, Constantinos; Frongillo, Rafael; Papadimitriou, Christos H.; Pierrakos, George; Valiant, Gregory 4 2010 An impossibility theorem for price-adjustment mechanisms. Zbl 1205.91067Papadimitriou, Christos H.; Yannakakis, Mihalis 3 2010 The complexity of computing a Nash equilibrium. Zbl 1185.91019Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H. 144 2009 Worst-case equilibria. Zbl 1303.91012Koutsoupias, Elias; Papadimitriou, Christos 122 2009 The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03024Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza; Papadimitriou, Christos H. 57 2009 A note on approximate Nash equilibria. Zbl 1167.91390Daskalakis, Constantinos; Mehta, Aranyak; Papadimitriou, Christos 36 2009 On oblivious PTAS’s for Nash equilibrium. Zbl 1304.91014Daskalakis, Constantinos; Papadimitriou, Christos H. 20 2009 Congestion games with malicious players. Zbl 1173.91301Babaioff, Moshe; Kleinberg, Robert; Papadimitriou, Christos H. 12 2009 On a network generalization of the minmax theorem. Zbl 1248.91006Daskalakis, Constantinos; Papadimitriou, Christos H. 7 2009 A note on strictly competitive games. Zbl 1377.91006Adler, Ilan; Daskalakis, Constantinos; Papadimitriou, Christos H. 4 2009 Logicomix. An epic search for truth. Character design and drawings by Alecos Papadatos, color by Annie Di Donna. Zbl 1248.00011Doxiadis, Apostolos; Papadimitriou, Christos H. 2 2009 Computing correlated equilibria in multi-player games. Zbl 1314.91012Papadimitriou, Christos H.; Roughgarden, Tim 43 2008 Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V. 38 2008 The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. Zbl 1192.68357Fabrikant, Alex; Papadimitriou, Christos H. 11 2008 On the complexity of reconfiguration problems. Zbl 1183.68310Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi 8 2008 The myth of the folk theorem. Zbl 1231.91006Borgs, Christian; Chayes, Jennifer; Immortica, Nicole; Kalai, Adam Tauman; Mirrokni, Vahab; Papadimitriou, Christos 5 2008 Linked decompositions of networks and the power of choice in Pólya urns. Zbl 1192.90027Lin, Henry; Amanatidis, Christos; Sideri, Martha; Karp, Richard M.; Papadimitriou, Christos H. 3 2008 Incentive-compatible interdomain routing with linear utilities. Zbl 1195.90019Hall, Alexander; Nikolova, Evdokia; Papadimitriou, Christos 1 2008 Inverval scheduling: a survey. Zbl 1143.90337Kolen, Antoon W. J.; Lenstra, Jan Karel; Papadimitriou, Christos H.; Spieksma, Frits C. R. 56 2007 Approximately dominating representatives. Zbl 1108.68042Koltun, Vladlen; Papadimitriou, Christos H. 18 2007 The complexity of finding Nash equilibria. Zbl 1151.91381Papadimitriou, Christos H. 15 2007 The complexity of computing a Nash equilibrium. Zbl 1301.68142Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H. 72 2006 Reducibility among equilibrium problems. Zbl 1301.68161Goldberg, Paul W.; Papadimitriou, Christos H. 18 2006 On the approximability of the traveling salesman problem. Zbl 1106.90071Papadimitriou, Christos H.; Vempala, Santosh 17 2006 Recognizing hole-free 4-map graphs in cubic time. Zbl 1095.68076Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. 15 2006 On certain connectivity properties of the internet topology. Zbl 1090.68002Mihail, Milena; Papadimitriou, Christos; Saberi, Amin 14 2006 The game world is flat: the complexity of Nash equilibria in succinct games. Zbl 1223.91008Daskalakis, Constantinos; Fabrikant, Alex; Papadimitriou, Christos H. 9 2006 The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03023Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza N.; Papadimitriou, Christos H. 7 2006 On a conjecture related to geometric routing. Zbl 1079.68078Papadimitriou, Christos H.; Ratajczak, David 38 2005 Computing equilibria in multi-player games. Zbl 1297.91005Papadimitriou, Christos H.; Roughgarden, Tim 19 2005 Computing correlated equilibria in multi-player games. Zbl 1192.91021Papadimitriou, Christos H. 17 2005 A BGP-based mechanism for lowest-cost routing. Zbl 1264.68215Feigenbaum, Joan; Papadimitriou, Christos; Sami, Rahul; Shenker, Scott 12 2005 The complexity of games on highly regular graphs. Zbl 1162.91306Daskalakis, Konstantinos; Papadimitriou, Christos H. 11 2005 The complexity of low-distortion embeddings between point sets. Zbl 1297.68246Papadimitriou, Christos; Safra, Shmuel 10 2005 Approximately dominating representatives. Zbl 1108.68446Koltun, Vladlen; Papadimitriou, Christos H. 5 2005 Approximating the distortion. Zbl 1142.68612Hall, Alexander; Papadimitriou, Christos 3 2005 The complexity of pure Nash equilibria. Zbl 1192.91042Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal 134 2004 Segmentation problems. Zbl 1317.90329Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar 17 2004 An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1181.91077Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva 7 2004 Global synchronization in sensornets. Zbl 1196.68024Elson, Jeremy; Karp, Richard M.; Papadimitriou, Christos H.; Shenker, Scott 6 2004 Selfish caching in distributed systems, a game-theoretic analysis. Zbl 1321.68068Chun, Byung-Gon; Chaudhuri, Kamalika; Wee, Hoeteck; Barreno, Marco; Papadimitriou, Christos H.; Kubiatowicz, John 6 2004 On a conjecture related to geometric routing. Zbl 1104.68328Papadimitriou, Christos H.; Ratajczak, David 3 2004 On a network creation game. Zbl 1322.91013Fabrikant, Alex; Luthra, Ankur; Maneva, Elitza; Papadimitriou, Christos H.; Shenker, Scott 82 2003 An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1094.68528Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva 22 2003 On the complexity of price equilibria. Zbl 1067.90102Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel 14 2003 On the complexity of single-rule datalog queries. Zbl 1055.68033Gottlob, Georg; Papadimitriou, Christos 10 2003 Auditing Boolean attributes. Zbl 1026.68042Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar 7 2003 A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe 43 2002 Map graphs. Zbl 1323.05039Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. 31 2002 Heuristically optimized trade-offs: A new paradigm for power laws in the internet. Zbl 1056.68503Fabrikant, Alex; Koutsoupias, Elias; Papadimitriou, Christos H. 15 2002 On the complexity of equilibria. Zbl 1192.91145Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel 12 2002 On the eigenvalue power law. Zbl 1028.68569Mihail, Milena; Papadimitriou, Christos 8 2002 A BGP-based mechanism for lowest-cost routing. Zbl 1292.68152Feigenbaum, Joan; Papadimitriou, Christos; Sami, Rahul; Shenker, Scott 8 2002 On a model of indexability and its bounds for range queries. Zbl 1323.68252Hellerstein, Joseph M.; Koutsoupias, Elias; Miranker, Daniel P.; Papadimitriou, Christos H.; Samoladas, Vasilis 5 2002 Algorithms, games, and the internet. Zbl 1323.68022Papadimitriou, Christos 153 2001 Sharing the cost of multicast transmissions. Zbl 0996.68026Feigenbaum, Joan; Papadimitriou, Christos H.; Shenker, Scott 42 2001 Deciding stability and mortality of piecewise affine dynamical systems. Zbl 0973.68067Blondel, V. D.; Bournez, O.; Koiran, P.; Papadimitriou, C. H.; Tsitsiklis, J. N. 21 2001 Algorithms, games, and the internet (extended abstract). Zbl 0986.68566Papadimitriou, Christos H. 19 2001 On approximating a scheduling problem. Zbl 1066.90027Crescenzi, Pierluigi; Deng, Xiaotie; Papadimitriou, Christos H. 6 2001 Latent semantic indexing: A probabilistic analysis. Zbl 0963.68063Papadimitriou, Christos H.; Raghavan, Prabhakar; Tamaki, Hisao; Vempala, Santosh 46 2000 Beyond competitive analysis. Zbl 0959.68131Koutsoupias, Elias; Papadimitriou, Christos H. 37 2000 On the approximability of the traveling salesman problem (extended abstract). Zbl 1296.68083Papadimitriou, Christos H.; Vempala, Santosh 12 2000 On the difficulty of designing good classifiers. Zbl 0959.68044Grigni, Michelangelo; Mirelli, Vincent; Papadimitriou, Christos H. 2 2000 Sharing the cost of muliticast transmissions (preliminary version). Zbl 1296.68066Feigenbaum, Joan; Papadimitriou, Christos; Shenker, Scott 1 2000 Worst-case equilibria. Zbl 1099.91501Koutsoupias, Elias; Papadimitriou, Christos 362 1999 Exploring an unknown graph. Zbl 0941.68099Deng, Xiaotie; Papadimitriou, Christos H. 42 1999 The complexity of optimal queuing network control. Zbl 0977.90008Papadimitriou, Christos H.; Tsitsiklis, John N. 39 1999 ...and 142 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 9,700 Authors 69 Papadimitriou, Christos Harilaos 41 Spirakis, Paul G. 37 Paschos, Vangelis Th. 34 Fomin, Fedor V. 34 Ito, Takehiro 32 Eiter, Thomas 30 Bilò, Vittorio 30 Monnot, Jérôme 30 Woeginger, Gerhard 28 Rothe, Jörg-Matthias 26 Deng, Xiao-Tie 26 Yang, Boting 25 Flammini, Michele 25 Makino, Kazuhisa 25 Wooldridge, Michael J. 24 Bazgan, Cristina 24 Ibaraki, Toshihide 24 Saurabh, Saket 24 Yannakakis, Mihalis 23 Epstein, Leah 23 Goldberg, Paul W. 22 Golovach, Petr A. 22 Monien, Burkhard 22 Subramani, Krishnan 21 Demaine, Erik D. 20 Escoffier, Bruno 20 Gottlob, Georg 20 Mavronicolas, Marios 19 Kreinovich, Vladik Yakovlevich 19 Moscardelli, Luca 19 Pelc, Andrzej 19 Vazirani, Vijay V. 18 Dereniowski, Dariusz 18 Fotakis, Dimitris A. 18 Lohrey, Markus 18 Niedermeier, Rolf 17 Demange, Marc 17 Kratsch, Dieter 17 Raman, Venkatesh 17 Szeider, Stefan 17 Thilikos, Dimitrios M. 16 Fearnley, John 16 Hromkovič, Juraj 16 Koutsoupias, Elias 16 Ye, Yinyu 15 Boros, Endre 15 Bose, Prosenjit K. 15 Chatterjee, Krishnendu 15 Deĭneko, Vladimir G. 15 Flocchini, Paola 15 Goldberg, Leslie Ann 15 Gutin, Gregory Z. 15 Hoefer, Martin 15 Mauri, Giancarlo 15 Mitchell, Joseph S. B. 15 Monaco, Gianpiero 15 Nisse, Nicolas 14 Bodlaender, Hans L. 14 Chen, Jian-er 14 de Figueiredo, Celina M. Herrera 14 Fraigniaud, Pierre 14 Heggernes, Pinar 14 Porreca, Antonio E. 14 Rizzi, Romeo 14 Savani, Rahul 14 Sudborough, Ivan Hal 14 Xu, Yinfeng 13 Arkin, Esther M. 13 Christodoulou, George C. 13 Creignou, Nadia 13 Deligkas, Argyrios 13 Fanelli, Angelo 13 Gairing, Martin 13 Jiang, Tao 13 Lampis, Michael 13 López-Ortiz, Alejandro 13 Lukasiewicz, Thomas 13 Maheshwari, Anil 13 Marx, Dániel 13 Mehlhorn, Kurt 13 Mehta, Ruta 13 Mirrokni, Vahab S. 13 Pardalos, Panos M. 13 Roughgarden, Tim 13 Suzuki, Akira 13 Tamir, Tami 13 Vollmer, Heribert 13 Wang, Lusheng 12 Bampis, Evripidis 12 Bentz, Cédric 12 Bertsekas, Dimitri Panteli 12 Caragiannis, Ioannis 12 Elkind, Edith 12 Faria, Luerbio 12 Fernau, Henning 12 Hansen, Pierre 12 Harvey, David I. 12 Ilcinkas, David 12 Jonsson, Peter 12 Kanj, Iyad A. ...and 9,600 more Authors all top 5 Cited in 488 Serials 852 Theoretical Computer Science 434 Discrete Applied Mathematics 278 European Journal of Operational Research 260 Journal of Computer and System Sciences 248 Algorithmica 231 Information Processing Letters 228 Artificial Intelligence 147 Theory of Computing Systems 141 Information and Computation 133 Journal of Combinatorial Optimization 122 Computers & Operations Research 114 Operations Research Letters 113 Mathematical Programming. Series A. Series B 94 Games and Economic Behavior 92 Annals of Operations Research 85 Discrete Mathematics 75 Annals of Mathematics and Artificial Intelligence 57 Computational Geometry 57 Journal of Discrete Algorithms 55 Discrete Optimization 46 Networks 45 SIAM Journal on Computing 45 Journal of Scheduling 43 Acta Informatica 42 Mathematics of Operations Research 41 International Journal of Approximate Reasoning 39 International Journal of Foundations of Computer Science 38 Discrete & Computational Geometry 38 Distributed Computing 36 Linear Algebra and its Applications 32 SIAM Journal on Discrete Mathematics 32 Journal of Global Optimization 31 International Journal of Computational Geometry & Applications 30 Annals of Pure and Applied Logic 29 Information Sciences 29 Optimization Letters 25 Operations Research 24 Applied Mathematics and Computation 23 Journal of Combinatorial Theory. Series B 23 Mathematical Social Sciences 22 Journal of Complexity 22 Cybernetics and Systems Analysis 21 SIAM Journal on Algebraic and Discrete Methods 21 Machine Learning 21 Computational Complexity 20 International Journal of Game Theory 20 RAIRO. Operations Research 19 Constraints 19 Computer Science Review 18 The Journal of Symbolic Logic 18 Optimization 18 Games 17 Journal of Graph Theory 17 RAIRO. Theoretical Informatics and Applications 16 Computing 16 Journal of Economic Theory 16 European Journal of Combinatorics 16 International Journal of Algebra and Computation 16 Quantum Information Processing 15 Automatica 15 Mathematical Programming 15 Journal of Automated Reasoning 15 Computational Optimization and Applications 15 The Journal of Artificial Intelligence Research (JAIR) 15 INFORMS Journal on Computing 15 4OR 15 Discrete Mathematics, Algorithms and Applications 14 International Journal of Computer Mathematics 14 Formal Methods in System Design 14 Optimization Methods & Software 14 International Game Theory Review 14 ACM Transactions on Computational Logic 14 Journal of Applied Logic 13 Combinatorica 13 Pattern Recognition 13 RAIRO. Informatique Théorique et Applications 13 Economic Theory 13 Mathematical Methods of Operations Research 13 CEJOR. Central European Journal of Operations Research 13 Logical Methods in Computer Science 12 Computers & Mathematics with Applications 12 Mathematics of Computation 12 Fuzzy Sets and Systems 12 Mathematical Systems Theory 12 Naval Research Logistics 12 Mathematical and Computer Modelling 12 Discrete Event Dynamic Systems 12 Automation and Remote Control 12 Mathematical Problems in Engineering 11 Journal of Statistical Physics 11 Graphs and Combinatorics 11 Journal of Heuristics 11 Algorithms 10 Journal of Mathematical Economics 10 Advances in Applied Mathematics 10 Physica D 10 Social Choice and Welfare 10 Journal of Symbolic Computation 10 Journal of Parallel and Distributed Computing 10 Random Structures & Algorithms ...and 388 more Serials all top 5 Cited in 54 Fields 4,376 Computer science (68-XX) 2,367 Operations research, mathematical programming (90-XX) 1,517 Combinatorics (05-XX) 1,287 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 434 Mathematical logic and foundations (03-XX) 248 Numerical analysis (65-XX) 148 Biology and other natural sciences (92-XX) 138 Information and communication theory, circuits (94-XX) 124 Convex and discrete geometry (52-XX) 121 Statistics (62-XX) 101 Probability theory and stochastic processes (60-XX) 82 Systems theory; control (93-XX) 70 Quantum theory (81-XX) 68 Group theory and generalizations (20-XX) 61 Order, lattices, ordered algebraic structures (06-XX) 57 Linear and multilinear algebra; matrix theory (15-XX) 48 Number theory (11-XX) 38 Calculus of variations and optimal control; optimization (49-XX) 37 Statistical mechanics, structure of matter (82-XX) 34 Dynamical systems and ergodic theory (37-XX) 21 Algebraic geometry (14-XX) 19 General algebraic systems (08-XX) 16 Manifolds and cell complexes (57-XX) 15 General topology (54-XX) 13 Field theory and polynomials (12-XX) 12 Operator theory (47-XX) 11 General and overarching topics; collections (00-XX) 11 Geometry (51-XX) 10 Measure and integration (28-XX) 10 Differential geometry (53-XX) 9 Commutative algebra (13-XX) 9 Mechanics of particles and systems (70-XX) 8 History and biography (01-XX) 8 Functional analysis (46-XX) 7 Fluid mechanics (76-XX) 6 Partial differential equations (35-XX) 6 Algebraic topology (55-XX) 6 Mechanics of deformable solids (74-XX) 5 Real functions (26-XX) 4 Category theory; homological algebra (18-XX) 4 Relativity and gravitational theory (83-XX) 4 Geophysics (86-XX) 3 Ordinary differential equations (34-XX) 3 Approximations and expansions (41-XX) 3 Optics, electromagnetic theory (78-XX) 3 Astronomy and astrophysics (85-XX) 2 Functions of a complex variable (30-XX) 2 Special functions (33-XX) 2 Integral transforms, operational calculus (44-XX) 2 Global analysis, analysis on manifolds (58-XX) 2 Mathematics education (97-XX) 1 Several complex variables and analytic spaces (32-XX) 1 Difference and functional equations (39-XX) 1 Classical thermodynamics, heat transfer (80-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.