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