×

zbMATH — the first resource for mathematics

Papadimitriou, Christos Harilaos

Compute Distance To:
Author ID: papadimitriou.christos-h Recent zbMATH articles by "Papadimitriou, Christos Harilaos"
Published as: Papadimitriou, Christos H.; Papadimitriou, Christos; Papadimitriou, C. H.; Paradimitriou, Christos H.; Papadimtriou, Christos; Papadimitriou, Ch. H.
External Links: MGP · Wikidata · dblp · GND · IdRef
Documents Indexed: 277 Publications since 1976, including 13 Books
Biographic References: 2 Publications
all top 5

Co-Authors

46 single-authored
29 Yannakakis, Mihalis
16 Sideri, Martha
13 Daskalakis, Constantinos
12 Koutsoupias, Elias
11 Deng, Xiao-Tie
9 Tsitsiklis, John N.
7 Afrati, Foto N.
7 Goldberg, Paul W.
7 Johnson, David Stifler
6 Grigni, Michelangelo
6 Kanellakis, Paris Christos
6 Papageorgiou, George
6 Shenker, Scott J.
6 Steiglitz, Kenneth
5 Fabrikant, Alex
5 Pierrakos, George
5 Raghavan, Prabhakar
5 Rubinstein, Aviad
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.
4 Vempala, Santosh S.
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 Safra, Shmuel
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 Piliouras, Georgios
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 105 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
4 Information and Computation
4 Games and Economic Behavior
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 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

Publications by Year

Citations contained in zbMATH Open

233 Publications have been cited 8,120 times in 6,516 Documents Cited by Year
Computational complexity. Zbl 0833.68049
Papadimitriou, Christos H.
760
1994
Combinatorial optimization: algorithms and complexity. Zbl 0503.90060
Papadimitriou, Christos H.; Steiglitz, Kenneth
706
1982
Computational complexity. Zbl 0557.68033
Papadimitriou, C. H.
410
1985
Optimization, approximation, and complexity classes. Zbl 0765.68036
Papadimitriou, Christos H.; Yannakakis, Mihalis
391
1991
Worst-case equilibria. Zbl 1099.91501
Koutsoupias, Elias; Papadimitriou, Christos
307
1999
Combinatorial optimization: algorithms and complexity. Corr. repr. of the 1982 original. Zbl 0944.90066
Papadimitriou, Christos H.; Steiglitz, Kenneth
210
1998
The complexity of multiterminal cuts. Zbl 0809.68075
Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.
174
1994
On generating all maximal independent sets. Zbl 0654.68086
Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H.
166
1988
Algorithms, games, and the internet. Zbl 1323.68022
Papadimitriou, Christos
141
2001
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
131
1988
On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048
Papadimitriou, Christos H.
121
1994
The complexity of pure Nash equilibria. Zbl 1192.91042
Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal
115
2004
The complexity of computing a Nash equilibrium. Zbl 1185.91019
Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H.
107
2009
Hamilton paths in grid graphs. Zbl 0506.05043
Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz
104
1982
The complexity of searching a graph. Zbl 0637.68081
Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H.
103
1988
Worst-case equilibria. Zbl 1303.91012
Koutsoupias, Elias; Papadimitriou, Christos
101
2009
The NP-completeness of the bandwidth minimization problem. Zbl 0321.65019
Papadimitriou, Ch. H.
98
1976
Searching and pebbling. Zbl 0616.68064
Kirousis, Lefteris M.; Papadimitriou, Christos H.
95
1986
The Euclidean traveling salesman problem is NP-complete. Zbl 0386.90057
Papadimitriou, Christos H.
93
1977
The complexity of facets (and some facets of complexity). Zbl 0571.68028
Papadimitriou, C. H.; Yannakakis, M.
92
1984
The complexity of coloring circular arcs and chords. Zbl 0499.05058
Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H.
90
1980
The traveling salesman problem with distances one and two. Zbl 0778.90057
Papadimitriou, Christos H.; Yannakakis, Mihalis
85
1993
On the complexity of cooperative solution concepts. Zbl 0824.90146
Deng, Xiaotie; Papadimitriou, Christos H.
84
1994
Shortest paths without a map. Zbl 0733.68065
Papadimitriou, Christos H.; Yannakakis, Mihalis
77
1991
On a network creation game. Zbl 1322.91013
Fabrikant, Alex; Luthra, Ankur; Maneva, Elitza; Papadimitriou, Christos H.; Shenker, Scott
76
2003
Elements of the theory of computation. Zbl 0464.68001
Lewis, Harry R.; Papadimitriou, Christos H.
76
1981
The discrete geodesic problem. Zbl 0625.68051
Mitchell, Joseph S. B.; Mount, David M.; Papadimitriou, Christos H.
66
1987
The complexity of computing a Nash equilibrium. Zbl 1301.68142
Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H.
66
2006
On the complexity of reconfiguration problems. Zbl 1207.68166
Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi
65
2011
The serializability of concurrent database updates. Zbl 0419.68036
Papadimitriou, Christos H.
63
1979
The complexity of Markov decision processes. Zbl 0638.90099
Papadimitriou, Christos H.; Tsitsiklis, John N.
62
1987
On the complexity of integer programming. Zbl 0468.68050
Papadimitriou, Christos H.
61
1981
Scheduling interval-ordered tasks. Zbl 0421.68040
Papadimitriou, C. H.; Yannakakis, M.
59
1979
Bounds for sorting by prefix reversal. Zbl 0397.68062
Gates, William H.; Papadimitriou, Christos H.
58
1979
Inverval scheduling: a survey. Zbl 1143.90337
Kolen, Antoon W. J.; Lenstra, Jan Karel; Papadimitriou, Christos H.; Spieksma, Frits C. R.
53
2007
Probabilistic satisfiability. Zbl 0647.68049
Georgakopoulos, George; Kavvadias, Dimitris; Papadimitriou, Christos H.
50
1988
The complexity of facets resolved. Zbl 0655.68041
Papadimitriou, Christos H.; Wolfe, David
49
1988
Flowshop scheduling with limited temporary storage. Zbl 0475.68014
Papadimitriou, Christos H.; Kanellakis, Paris C.
47
1980
On the \(k\)-server conjecture. Zbl 0885.68075
Koutsoupias, Elias; Papadimitriou, Christos H.
47
1995
The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03024
Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza; Papadimitriou, Christos H.
46
2009
Interval graphs and searching. Zbl 0566.05056
Kirousis, Lefteris M.; Papadimitriou, Christos H.
45
1985
The weighted region problem: Finding shortest paths through a weighted planar subdivision. Zbl 0799.68150
Mitchell, Joseph S. B.; Papadimitriou, Christos H.
45
1991
The complexity of restricted spanning tree problems. Zbl 0478.68068
Papadimitriou, Christos H.; Yannakakis, Mihalis
44
1982
Latent semantic indexing: A probabilistic analysis. Zbl 0963.68063
Papadimitriou, Christos H.; Raghavan, Prabhakar; Tamaki, Hisao; Vempala, Santosh
40
2000
On total functions, existence theorems and computational complexity. Zbl 0731.68036
Megiddo, Nimrod; Papadimitriou, Christos H.
40
1991
Games against nature. Zbl 0583.68020
Papadimitriou, Christos H.
39
1985
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe
39
2002
Sharing the cost of multicast transmissions. Zbl 0996.68026
Feigenbaum, Joan; Papadimitriou, Christos H.; Shenker, Scott
38
2001
Symmetric space-bounded computation. Zbl 0491.68045
Lewis, Harry R.; Papadimitriou, Christos H.
38
1982
The complexity of the travelling repairman problem. Zbl 0585.68057
Afrati, Foto; Cosmadakis, Stavros; Papadimitriou, Christos H.; Papageorgiou, George; Papakostantinou, Nadia
37
1986
Exploring an unknown graph. Zbl 0941.68099
Deng, Xiaotie; Papadimitriou, Christos H.
37
1999
Beyond competitive analysis. Zbl 0959.68131
Koutsoupias, Elias; Papadimitriou, Christos H.
36
2000
On limited nondeterminism and the complexity of the V-C dimension. Zbl 0859.68031
Papadimitriou, Christos H.; Yannakakis, Mihalis
36
1996
On two geometric problems related to the travelling salesman problem. Zbl 0551.90093
Papadimitriou, Christos H.; Vazirani, Umesh V.
35
1984
On a conjecture related to geometric routing. Zbl 1079.68078
Papadimitriou, Christos H.; Ratajczak, David
35
2005
Topological bandwidth. Zbl 0573.05052
Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H.
34
1985
How to learn an unknown environment. I: The rectilinear case. Zbl 0904.68115
Deng, Xiaotie; Kameda, Tiko; Papadimitriou, Christos
33
1998
Towards an architecture-independent analysis of parallel algorithms. Zbl 0692.68032
Papadimitriou, Christos H.; Yannakakis, Mihalis
33
1990
Computing correlated equilibria in multi-player games. Zbl 1314.91012
Papadimitriou, Christos H.; Roughgarden, Tim
32
2008
Worst-case and probabilistic analysis of a geometric location problem. Zbl 0461.68078
Papadimitriou, Christos H.
32
1981
On the complexity of edge traversing. Zbl 0351.90079
Papadimitriou, Christos H.
32
1976
The complexity of optimal queuing network control. Zbl 0977.90008
Papadimitriou, Christos H.; Tsitsiklis, John N.
31
1999
The adjacency relation on the traveling salesman polytope is NP-complete. Zbl 0376.90067
Papadimitriou, Christos H.
31
1978
Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024
Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V.
29
2008
The theory of database concurrency control. Zbl 0609.68073
Papadimitriou, Christos
29
1986
A note on approximate Nash equilibria. Zbl 1167.91390
Daskalakis, Constantinos; Mehta, Aranyak; Papadimitriou, Christos
28
2009
Communication complexity. Zbl 0584.68064
Papadimitriou, Christos H.; Sipser, Michael
26
1984
Inclusion dependencies and their interaction with functional dependencies. Zbl 0586.68082
Casanova, Marco A.; Fagin, Ronald; Papadimitriou, Christos H.
26
1984
On linear characterizations of combinatorial optimization problems. Zbl 0505.65020
Karp, Richard M.; Papadimitriou, Christos H.
26
1982
An algorithm for shortest-path motion in three dimensions. Zbl 0603.68070
Papadimitriou, Christos H.
25
1985
Why not negation by fixpoint? Zbl 0753.68028
Kolaitis, Phokion G.; Papadimitriou, Christos H.
25
1991
Some examples of difficult traveling salesman problems. Zbl 0383.90105
Papadimitriou, C. H.; Steiglitz, K.
25
1978
Map graphs. Zbl 1323.05039
Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H.
24
2002
On Horn envelopes and hypergraph transversals. (Extended abstract). Zbl 0925.03036
Kavvdias, Dimitris; Papadimitriou, Christos; Sideri, Martha
24
1993
On the complexity of database queries. Zbl 0939.68024
Papadimitriou, Christos H.; Yannakakis, Mihalis
24
1999
Exponential lower bounds for finding Brouwer fixed points. Zbl 0696.65045
Hirsch, Michael D.; Papadimitriou, Christos H.; Vavasis, Stephen A.
24
1989
The complexity of the capacitated tree problem. Zbl 0443.68048
Papadimitriou, C. H.
23
1978
A linear programming approach to reasoning about probabilities. Zbl 0878.68034
Kavvadias, Dimitris; Papadimitriou, Christos H.
22
1990
An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1094.68528
Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva
21
2003
A note on succinct representations of graphs. Zbl 0616.68041
Papadimitriou, Christos H.; Yannakakis, Mihalis
20
1986
Local search for the asymmetric traveling salesman problem. Zbl 0447.90082
Kanellakis, Paris-C.; Papadimitriou, Christos H.
20
1980
Covering graphs by simple circuits. Zbl 0468.68071
Itai, Alon; Lipton, Richard J.; Papadimitriou, Christos H.; Rodeh, M.
20
1981
On complexity as bounded rationality (extended abstract). Zbl 1345.68216
Papadimitriou, Christos H.; Yannakakis, Mihalis
18
1994
On the complexity of protein folding (extended abstract). Zbl 1007.68511
Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis
18
1998
The even-path problem for graphs and digraphs. Zbl 0552.68059
LaPaugh, Andrea S.; Papadimitriou, Christos H.
18
1984
Searching a fixed graph. Zbl 1045.90532
Koutsoupias, Elias; Papadimitriou, Christos; Yannakakis, Mihalis
18
1996
Deciding stability and mortality of piecewise affine dynamical systems. Zbl 0973.68067
Blondel, V. D.; Bournez, O.; Koiran, P.; Papadimitriou, C. H.; Tsitsiklis, J. N.
18
2001
Computing correlated equilibria in multi-player games. Zbl 1192.91021
Papadimitriou, Christos H.
17
2005
On oblivious PTAS’s for Nash equilibrium. Zbl 1304.91014
Daskalakis, Constantinos; Papadimitriou, Christos H.
17
2009
Computing equilibria in multi-player games. Zbl 1297.91005
Papadimitriou, Christos H.; Roughgarden, Tim
17
2005
Efficient search for rationals. Zbl 0411.65037
Papadimitriou, Christos H.
17
1979
Planar map graphs. Zbl 1028.68104
Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H.
16
1998
Performance guarantees for heuristics. Zbl 0574.90086
Johnson, D. S.; Papadimitriou, C. H.
16
1985
Continuous local search. Zbl 1373.68263
Daskalakis, Constantinos; Papadimitriou, Christos
16
2011
Reducibility among equilibrium problems. Zbl 1301.68161
Goldberg, Paul W.; Papadimitriou, Christos H.
16
2006
On the approximability of the traveling salesman problem. Zbl 1106.90071
Papadimitriou, Christos H.; Vempala, Santosh
15
2006
NP-completeness: a retrospective. Zbl 1401.68100
Papadimitriou, Christos H.
15
1997
Algorithms, games, and the internet (extended abstract). Zbl 0986.68566
Papadimitriou, Christos H.
15
2001
On players with a bounded number of states. Zbl 0767.90097
Papadimitriou, Christos H.
15
1992
On the complexity of local search for the traveling salesman problem. Zbl 0381.68043
Papadimitriou, Christos H.; Steiglitz, Kenneth
15
1977
Towards a unified complexity theory of total functions. Zbl 1393.68053
Goldberg, Paul W.; Papadimitriou, Christos H.
6
2018
Cycles in adversarial regularized learning. Zbl 1403.68200
Mertikopoulos, Panayotis; Papadimitriou, Christos; Piliouras, Georgios
4
2018
From battlefields to elections: winning strategies of Blotto and auditing games. Zbl 1403.91013
Behnezhad, 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.68235
Gaspers, Serge; Papadimitriou, Christos H.; Sæther, Sigve Hortemo; Telle, Jan Arne
4
2017
TFNP: an update. Zbl 06751046
Goldberg, Paul W.; Papadimitriou, Christos H.
2
2017
Stathis zachos at 70! Zbl 06751084
Bakali, 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.91009
Cai, Yang; Candogan, Ozan; Daskalakis, Constantinos; Papadimitriou, Christos
5
2016
Can almost everybody be almost happy? Zbl 1335.91021
Babichenko, Yakov; Papadimitriou, Christos; Rubinstein, Aviad
3
2016
From Nash equilibria to chain recurrent sets: solution concepts and topology. Zbl 1335.91009
Papadimitriou, Christos; Piliouras, Georgios
3
2016
Locally adaptive optimization: adaptive seeding for monotone submodular functions. Zbl 1423.90157
Badanidiyuru, Ashwinkumar; Papadimitriou, Christos; Rubinstein, Aviad; Seeman, Lior; Singer, Yaron
1
2016
On the complexity of dynamic mechanism design. Zbl 1417.91247
Papadimitriou, Christos; Pierrakos, George; Psomas, Christos-Alexandros; Rubinstein, Aviad
1
2016
Approximate Nash equilibria in anonymous games. Zbl 1330.91015
Daskalakis, Constantinos; Papadimitriou, Christos H.
14
2015
Sparse covers for sums of indicators. Zbl 1334.60048
Daskalakis, Constantinos; Papadimitriou, Christos
5
2015
Optimal deterministic auctions with correlated priors. Zbl 1318.91102
Papadimitriou, Christos; Pierrakos, George
2
2015
Algorithms, games, and evolution. Zbl 1355.91017
Chastain, Erick; Livnat, Adi; Papadimitriou, Christos; Vazirani, Umesh
13
2014
On simplex pivoting rules and complexity theory. Zbl 1418.90145
Adler, Ilan; Papadimitriou, Christos; Rubinstein, Aviad
6
2014
Efficiency-revenue trade-offs in auctions. Zbl 1367.91077
Diakonikolas, Ilias; Papadimitriou, Christos; Pierrakos, George; Singer, Yaron
5
2012
On the complexity of reconfiguration problems. Zbl 1207.68166
Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi
65
2011
Continuous local search. Zbl 1373.68263
Daskalakis, Constantinos; Papadimitriou, Christos
16
2011
On optimal single-item auctions. Zbl 1288.90087
Papadimitriou, Christos H.; Pierrakos, George
9
2011
Modeling social networks through user background and behavior. Zbl 1328.91262
Foudalis, Ilias; Jain, Kamal; Papadimitriou, Christos; Sideri, Martha
4
2011
The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions. Zbl 1292.91013
Goldberg, Paul W.; Papadimitriou, Christos H.; Savani, Rahul
3
2011
Kurt Gödel and the foundations of mathematics. Horizons of truth. Zbl 1253.00009
Baaz, Matthias; Papadimitriou, Christos H.; Putnam, Hilary W.; Scott, Dana S.; Harper, Charles L. jun.
1
2011
An analytical contrast between fitness maximization and selection for mixability. Zbl 1405.92197
Livnat, Adi; Papadimitriou, Christos; M. W. Feldman, Marcus W.
1
2011
When the players are not expectation maximizers. Zbl 1253.91009
Fiat, Amos; Papadimitriou, Christos
10
2010
Inapproximability for VCG-based combinatorial auctions. Zbl 1288.91099
Buchfuhrer, Dave; Dughmi, Shaddin; Fu, Hu; Kleinberg, Robert; Mossel, Elchanan; Papadimitriou, Christos; Schapira, Michael; Singer, Yaron; Umans, Chris
9
2010
The myth of the folk theorem. Zbl 1207.91012
Borgs, Christian; Chayes, Jennifer; Immorlica, Nicole; Kalai, Adam Tauman; Mirrokni, Vahab; Papadimitriou, Christos
6
2010
On learning algorithms for Nash equilibria. Zbl 1310.91033
Daskalakis, Constantinos; Frongillo, Rafael; Papadimitriou, Christos H.; Pierrakos, George; Valiant, Gregory
4
2010
An impossibility theorem for price-adjustment mechanisms. Zbl 1205.91067
Papadimitriou, Christos H.; Yannakakis, Mihalis
3
2010
The complexity of computing a Nash equilibrium. Zbl 1185.91019
Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H.
107
2009
Worst-case equilibria. Zbl 1303.91012
Koutsoupias, Elias; Papadimitriou, Christos
101
2009
The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03024
Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza; Papadimitriou, Christos H.
46
2009
A note on approximate Nash equilibria. Zbl 1167.91390
Daskalakis, Constantinos; Mehta, Aranyak; Papadimitriou, Christos
28
2009
On oblivious PTAS’s for Nash equilibrium. Zbl 1304.91014
Daskalakis, Constantinos; Papadimitriou, Christos H.
17
2009
Congestion games with malicious players. Zbl 1173.91301
Babaioff, Moshe; Kleinberg, Robert; Papadimitriou, Christos H.
10
2009
On a network generalization of the minmax theorem. Zbl 1248.91006
Daskalakis, Constantinos; Papadimitriou, Christos H.
7
2009
A note on strictly competitive games. Zbl 1377.91006
Adler, 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.00011
Doxiadis, Apostolos; Papadimitriou, Christos H.
2
2009
Computing correlated equilibria in multi-player games. Zbl 1314.91012
Papadimitriou, Christos H.; Roughgarden, Tim
32
2008
Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024
Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V.
29
2008
The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. Zbl 1192.68357
Fabrikant, Alex; Papadimitriou, Christos H.
10
2008
On the complexity of reconfiguration problems. Zbl 1183.68310
Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi
7
2008
The myth of the folk theorem. Zbl 1231.91006
Borgs, Christian; Chayes, Jennifer; Immortica, Nicole; Kalai, Adam Tauman; Mirrokni, Vahab; Papadimitriou, Christos
4
2008
Linked decompositions of networks and the power of choice in Pólya urns. Zbl 1192.90027
Lin, Henry; Amanatidis, Christos; Sideri, Martha; Karp, Richard M.; Papadimitriou, Christos H.
2
2008
Incentive-compatible interdomain routing with linear utilities. Zbl 1195.90019
Hall, Alexander; Nikolova, Evdokia; Papadimitriou, Christos
1
2008
Inverval scheduling: a survey. Zbl 1143.90337
Kolen, Antoon W. J.; Lenstra, Jan Karel; Papadimitriou, Christos H.; Spieksma, Frits C. R.
53
2007
The complexity of finding Nash equilibria. Zbl 1151.91381
Papadimitriou, Christos H.
14
2007
Approximately dominating representatives. Zbl 1108.68042
Koltun, Vladlen; Papadimitriou, Christos H.
13
2007
The complexity of computing a Nash equilibrium. Zbl 1301.68142
Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H.
66
2006
Reducibility among equilibrium problems. Zbl 1301.68161
Goldberg, Paul W.; Papadimitriou, Christos H.
16
2006
On the approximability of the traveling salesman problem. Zbl 1106.90071
Papadimitriou, Christos H.; Vempala, Santosh
15
2006
Recognizing hole-free 4-map graphs in cubic time. Zbl 1095.68076
Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H.
13
2006
On certain connectivity properties of the internet topology. Zbl 1090.68002
Mihail, Milena; Papadimitriou, Christos; Saberi, Amin
13
2006
The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03023
Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza N.; Papadimitriou, Christos H.
7
2006
The game world is flat: the complexity of Nash equilibria in succinct games. Zbl 1223.91008
Daskalakis, Constantinos; Fabrikant, Alex; Papadimitriou, Christos H.
7
2006
On a conjecture related to geometric routing. Zbl 1079.68078
Papadimitriou, Christos H.; Ratajczak, David
35
2005
Computing correlated equilibria in multi-player games. Zbl 1192.91021
Papadimitriou, Christos H.
17
2005
Computing equilibria in multi-player games. Zbl 1297.91005
Papadimitriou, Christos H.; Roughgarden, Tim
17
2005
A BGP-based mechanism for lowest-cost routing. Zbl 1264.68215
Feigenbaum, Joan; Papadimitriou, Christos; Sami, Rahul; Shenker, Scott
11
2005
The complexity of games on highly regular graphs. Zbl 1162.91306
Daskalakis, Konstantinos; Papadimitriou, Christos H.
10
2005
The complexity of low-distortion embeddings between point sets. Zbl 1297.68246
Papadimitriou, Christos; Safra, Shmuel
10
2005
Approximately dominating representatives. Zbl 1108.68446
Koltun, Vladlen; Papadimitriou, Christos H.
3
2005
Approximating the distortion. Zbl 1142.68612
Hall, Alexander; Papadimitriou, Christos
1
2005
The complexity of pure Nash equilibria. Zbl 1192.91042
Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal
115
2004
Segmentation problems. Zbl 1317.90329
Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar
13
2004
An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1181.91077
Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva
7
2004
Selfish caching in distributed systems, a game-theoretic analysis. Zbl 1321.68068
Chun, Byung-Gon; Chaudhuri, Kamalika; Wee, Hoeteck; Barreno, Marco; Papadimitriou, Christos H.; Kubiatowicz, John
6
2004
Global synchronization in sensornets. Zbl 1196.68024
Elson, Jeremy; Karp, Richard M.; Papadimitriou, Christos H.; Shenker, Scott
5
2004
On a conjecture related to geometric routing. Zbl 1104.68328
Papadimitriou, Christos H.; Ratajczak, David
2
2004
On a network creation game. Zbl 1322.91013
Fabrikant, Alex; Luthra, Ankur; Maneva, Elitza; Papadimitriou, Christos H.; Shenker, Scott
76
2003
An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1094.68528
Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva
21
2003
On the complexity of price equilibria. Zbl 1067.90102
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
13
2003
On the complexity of single-rule datalog queries. Zbl 1055.68033
Gottlob, Georg; Papadimitriou, Christos
9
2003
Auditing Boolean attributes. Zbl 1026.68042
Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar
6
2003
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe
39
2002
Map graphs. Zbl 1323.05039
Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H.
24
2002
Heuristically optimized trade-offs: A new paradigm for power laws in the internet. Zbl 1056.68503
Fabrikant, Alex; Koutsoupias, Elias; Papadimitriou, Christos H.
14
2002
On the complexity of equilibria. Zbl 1192.91145
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
9
2002
A BGP-based mechanism for lowest-cost routing. Zbl 1292.68152
Feigenbaum, Joan; Papadimitriou, Christos; Sami, Rahul; Shenker, Scott
8
2002
On the eigenvalue power law. Zbl 1028.68569
Mihail, Milena; Papadimitriou, Christos
6
2002
On a model of indexability and its bounds for range queries. Zbl 1323.68252
Hellerstein, Joseph M.; Koutsoupias, Elias; Miranker, Daniel P.; Papadimitriou, Christos H.; Samoladas, Vasilis
5
2002
Algorithms, games, and the internet. Zbl 1323.68022
Papadimitriou, Christos
141
2001
Sharing the cost of multicast transmissions. Zbl 0996.68026
Feigenbaum, Joan; Papadimitriou, Christos H.; Shenker, Scott
38
2001
Deciding stability and mortality of piecewise affine dynamical systems. Zbl 0973.68067
Blondel, V. D.; Bournez, O.; Koiran, P.; Papadimitriou, C. H.; Tsitsiklis, J. N.
18
2001
Algorithms, games, and the internet (extended abstract). Zbl 0986.68566
Papadimitriou, Christos H.
15
2001
On approximating a scheduling problem. Zbl 1066.90027
Crescenzi, Pierluigi; Deng, Xiaotie; Papadimitriou, Christos H.
6
2001
Latent semantic indexing: A probabilistic analysis. Zbl 0963.68063
Papadimitriou, Christos H.; Raghavan, Prabhakar; Tamaki, Hisao; Vempala, Santosh
40
2000
Beyond competitive analysis. Zbl 0959.68131
Koutsoupias, Elias; Papadimitriou, Christos H.
36
2000
On the approximability of the traveling salesman problem (extended abstract). Zbl 1296.68083
Papadimitriou, Christos H.; Vempala, Santosh
11
2000
On the difficulty of designing good classifiers. Zbl 0959.68044
Grigni, Michelangelo; Mirelli, Vincent; Papadimitriou, Christos H.
2
2000
Sharing the cost of muliticast transmissions (preliminary version). Zbl 1296.68066
Feigenbaum, Joan; Papadimitriou, Christos; Shenker, Scott
1
2000
Worst-case equilibria. Zbl 1099.91501
Koutsoupias, Elias; Papadimitriou, Christos
307
1999
Exploring an unknown graph. Zbl 0941.68099
Deng, Xiaotie; Papadimitriou, Christos H.
37
1999
The complexity of optimal queuing network control. Zbl 0977.90008
Papadimitriou, Christos H.; Tsitsiklis, John N.
31
1999
On the complexity of database queries. Zbl 0939.68024
Papadimitriou, Christos H.; Yannakakis, Mihalis
24
1999
Topological queries in spatial databases. Zbl 0943.68051
Papadimitriou, C. H.; Suciu, D.; Vianu, V.
8
1999
Decision-making by hierarchies of discordant agents. Zbl 0939.90009
Deng, Xiaotie; Papadimitriou, Christos
4
1999
Combinatorial optimization: algorithms and complexity. Corr. repr. of the 1982 original. Zbl 0944.90066
Papadimitriou, Christos H.; Steiglitz, Kenneth
210
1998
How to learn an unknown environment. I: The rectilinear case. Zbl 0904.68115
Deng, Xiaotie; Kameda, Tiko; Papadimitriou, Christos
33
1998
On the complexity of protein folding (extended abstract). Zbl 1007.68511
Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis
18
1998
...and 133 more Documents
all top 5

Cited by 8,700 Authors

64 Papadimitriou, Christos Harilaos
37 Paschos, Vangelis Th.
35 Spirakis, Paul G.
30 Eiter, Thomas
30 Fomin, Fedor V.
30 Woeginger, Gerhard Johannes
29 Monnot, Jérôme
26 Bilò, Vittorio
25 Makino, Kazuhisa
24 Ibaraki, Toshihide
23 Bazgan, Cristina
23 Flammini, Michele
23 Yannakakis, Mihalis
22 Epstein, Leah
22 Ito, Takehiro
22 Monien, Burkhard
21 Demaine, Erik D.
21 Deng, Xiao-Tie
21 Wooldridge, Michael J.
21 Yang, Boting
20 Escoffier, Bruno
19 Goldberg, Paul W.
19 Golovach, Petr A.
19 Gottlob, Georg
19 Mavronicolas, Marios
19 Saurabh, Saket
19 Subramani, Krishnan
19 Vazirani, Vijay V.
18 Lohrey, Markus
17 Dereniowski, Dariusz
17 Kratsch, Dieter
17 Moscardelli, Luca
17 Niedermeier, Rolf
17 Pelc, Andrzej
17 Rothe, Jörg-Matthias
17 Szeider, Stefan
16 Demange, Marc
16 Kreinovich, Vladik Yakovlevich
16 Raman, Venkatesh
15 Boros, Endre
15 Deĭneko, Vladimir G.
15 Flocchini, Paola
15 Fotakis, Dimitris A.
15 Hromkovič, Juraj
15 Mitchell, Joseph S. B.
15 Nisse, Nicolas
15 Ye, Yinyu
14 Chen, Jian-er
14 Fraigniaud, Pierre
14 Goldberg, Leslie Ann
14 Gutin, Gregory Z.
14 Heggernes, Pinar
14 Koutsoupias, Elias
14 Mauri, Giancarlo
14 Porreca, Antonio E.
14 Sudborough, Ivan Hal
14 Xu, Yinfeng
13 Arkin, Esther M.
13 Creignou, Nadia
13 Fanelli, Angelo
13 Fearnley, John
13 Monaco, Gianpiero
13 Pardalos, Panos M.
13 Rizzi, Romeo
13 Savani, Rahul
13 Thilikos, Dimitrios M.
13 Wang, Lusheng
12 Bampis, Evripidis
12 Bentz, Cédric
12 Bertsekas, Dimitri Panteli
12 Bodlaender, Hans L.
12 Chatterjee, Krishnendu
12 Christodoulou, George C.
12 Faria, Luerbio
12 Fernau, Henning
12 Gairing, Martin
12 Hansen, Pierre
12 Hoefer, Martin
12 Ilcinkas, David
12 Jiang, Tao
12 Kanj, Iyad A.
12 Mirrokni, Vahab S.
12 Roughgarden, Tim
12 Santoro, Nicola
12 Serna, Maria José
12 Steiner, George
12 Tamir, Tami
12 Tsitsiklis, John N.
12 Uehara, Ryuhei
12 Vollmer, Heribert
11 Anshelevich, Elliot
11 Bose, Prosenjit K.
11 Caragiannis, Ioannis
11 de Figueiredo, Celina M. Herrera
11 Gagliardi Cozman, Fabio
11 Jonsson, Peter A.
11 Lampis, Michael
11 López-Ortiz, Alejandro
11 Lukasiewicz, Thomas
11 Maheshwari, Anil
...and 8,600 more Authors
all top 5

Cited in 453 Serials

803 Theoretical Computer Science
416 Discrete Applied Mathematics
260 European Journal of Operational Research
251 Journal of Computer and System Sciences
240 Algorithmica
228 Information Processing Letters
194 Artificial Intelligence
141 Theory of Computing Systems
127 Information and Computation
114 Operations Research Letters
112 Computers & Operations Research
105 Mathematical Programming. Series A. Series B
105 Journal of Combinatorial Optimization
85 Annals of Operations Research
85 Games and Economic Behavior
83 Discrete Mathematics
69 Annals of Mathematics and Artificial Intelligence
57 Journal of Discrete Algorithms
54 Computational Geometry
49 Discrete Optimization
46 Networks
43 Journal of Scheduling
41 Acta Informatica
39 International Journal of Foundations of Computer Science
36 International Journal of Approximate Reasoning
36 Distributed Computing
35 Discrete & Computational Geometry
35 Linear Algebra and its Applications
34 SIAM Journal on Computing
30 Journal of Global Optimization
29 Information Sciences
29 Mathematics of Operations Research
29 International Journal of Computational Geometry & Applications
27 Annals of Pure and Applied Logic
26 SIAM Journal on Discrete Mathematics
25 Optimization Letters
22 Journal of Combinatorial Theory. Series B
22 Journal of Complexity
22 Cybernetics and Systems Analysis
21 Applied Mathematics and Computation
21 Mathematical Social Sciences
21 SIAM Journal on Algebraic and Discrete Methods
21 Machine Learning
20 International Journal of Game Theory
20 Computational Complexity
20 RAIRO. Operations Research
19 Operations Research
18 Optimization
18 Constraints
17 Journal of Graph Theory
17 The Journal of Symbolic Logic
17 RAIRO. Theoretical Informatics and Applications
17 Computer Science Review
16 Computing
15 Journal of Economic Theory
15 Mathematical Programming
15 Journal of Automated Reasoning
15 International Journal of Algebra and Computation
15 Computational Optimization and Applications
15 4OR
14 Automatica
14 European Journal of Combinatorics
14 International Journal of Computer Mathematics
14 Journal of Applied Logic
13 Combinatorica
13 Pattern Recognition
13 RAIRO. Informatique Théorique et Applications
13 Games
12 Computers & Mathematics with Applications
12 Fuzzy Sets and Systems
12 Mathematical Systems Theory
12 Naval Research Logistics
12 Mathematical and Computer Modelling
12 Mathematical Problems in Engineering
12 Optimization Methods & Software
12 Mathematical Methods of Operations Research
12 Discrete Mathematics, Algorithms and Applications
11 Journal of Statistical Physics
11 Mathematics of Computation
11 Discrete Event Dynamic Systems
11 Formal Methods in System Design
11 Economic Theory
11 The Journal of Artificial Intelligence Research (JAIR)
11 Journal of Heuristics
11 INFORMS Journal on Computing
11 CEJOR. Central European Journal of Operations Research
11 ACM Transactions on Computational Logic
11 Algorithms
10 Journal of Mathematical Economics
10 Journal of Symbolic Computation
10 Journal of Parallel and Distributed Computing
10 Random Structures & Algorithms
10 Data Mining and Knowledge Discovery
10 Logical Methods in Computer Science
9 Journal of Optimization Theory and Applications
9 Advances in Applied Mathematics
9 OR Spektrum
9 International Journal of Production Research
9 Physica D
9 Social Choice and Welfare
...and 353 more Serials
all top 5

Cited in 55 Fields

3,903 Computer science (68-XX)
2,149 Operations research, mathematical programming (90-XX)
1,367 Combinatorics (05-XX)
1,085 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
400 Mathematical logic and foundations (03-XX)
235 Numerical analysis (65-XX)
136 Biology and other natural sciences (92-XX)
127 Information and communication theory, circuits (94-XX)
110 Convex and discrete geometry (52-XX)
103 Statistics (62-XX)
81 Probability theory and stochastic processes (60-XX)
73 Systems theory; control (93-XX)
60 Group theory and generalizations (20-XX)
59 Order, lattices, ordered algebraic structures (06-XX)
59 Quantum theory (81-XX)
51 Linear and multilinear algebra; matrix theory (15-XX)
41 Number theory (11-XX)
33 Calculus of variations and optimal control; optimization (49-XX)
31 Dynamical systems and ergodic theory (37-XX)
31 Statistical mechanics, structure of matter (82-XX)
21 Algebraic geometry (14-XX)
15 Manifolds and cell complexes (57-XX)
14 General topology (54-XX)
12 Operator theory (47-XX)
12 Geometry (51-XX)
11 General and overarching topics; collections (00-XX)
11 General algebraic systems (08-XX)
11 Field theory and polynomials (12-XX)
9 Commutative algebra (13-XX)
9 Differential geometry (53-XX)
8 Measure and integration (28-XX)
7 History and biography (01-XX)
7 Functional analysis (46-XX)
7 Mechanics of particles and systems (70-XX)
5 Real functions (26-XX)
5 Partial differential equations (35-XX)
5 Mechanics of deformable solids (74-XX)
4 Category theory; homological algebra (18-XX)
4 Fluid mechanics (76-XX)
4 Relativity and gravitational theory (83-XX)
3 Ordinary differential equations (34-XX)
3 Approximations and expansions (41-XX)
3 Algebraic topology (55-XX)
3 Optics, electromagnetic theory (78-XX)
3 Geophysics (86-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 Astronomy and astrophysics (85-XX)
2 Mathematics education (97-XX)
1 Associative rings and algebras (16-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.