Christos H. Papadimitriou

Orcid: 0009-0000-7264-8015

Affiliations:
  • Columbia University, New York, NY, USA
  • University of California, Berkeley, USA (former)


According to our database1, Christos H. Papadimitriou authored at least 398 papers between 1976 and 2024.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of three.

Awards

ACM Fellow

ACM Fellow 2001, "For outstanding contributions to complexity theory, database theory and combinatorial optimization.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
On Limitations of the Transformer Architecture.
CoRR, 2024

2023
Public goods games in directed networks.
Games Econ. Behav., May, 2023

The complexity of non-stationary reinforcement learning.
CoRR, 2023

The Architecture of a Biologically Plausible Language Organ.
CoRR, 2023

Computation with Sequences in the Brain.
CoRR, 2023

The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points.
Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Cook's NP-completeness Paper and the Dawn of the New Theory.
Proceedings of the Logic, 2023

2022
Bridging the Gap Between Neurons and Cognition Through Assemblies of Neurons.
Neural Comput., 2022

On the complexity of dynamic mechanism design.
Games Econ. Behav., 2022

Center-Embedding and Constituency in the Brain and a New Characterization of Context-Free Languages.
CoRR, 2022

Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics.
CoRR, 2022

Optimal Scheduling of the Leaves of a Tree and the SVO Frequencies of Languages.
Proceedings of the Learning and Intelligent Optimization - 16th International Conference, 2022

Memory Bounds for Continual Learning.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Assemblies of neurons learn to classify well-separated distributions.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Planning with Biological Neurons and Synapses.
Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021
Assemblies of neurons can learn to classify well-separated distributions.
CoRR, 2021

A Biologically Plausible Parser.
CoRR, 2021

Public Good Games in Directed Networks.
CoRR, 2021

The Platform Design Problem.
Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities.
Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Panel on "Past and Future of Computer Science Theory" (Discussion Paper).
Proceedings of the 29th Italian Symposium on Advanced Database Systems, 2021

Total Functions in the Polynomial Hierarchy.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Self-Attention Networks Can Process Bounded Hierarchical Languages.
Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, 2021

2020
Total Functions in the Polynomial Hierarchy.
Electron. Colloquium Comput. Complex., 2020

A New Age of Computing and the Brain.
CoRR, 2020

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019
Brain Computation: A Computer Science Perspective.
Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019

Reductions in PPP.
Inf. Process. Lett., 2019

α-Rank: Multi-Agent Evaluation by Evolution.
CoRR, 2019

Wealth Inequality and the Price of Anarchy.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Random Projection in the Brain and Computation with Assemblies of Neurons.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Energy Equilibria in Proof-of-Work Mining.
Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

Optimal Strategies of Blotto Games: Beyond Convexity.
Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

An Axiomatic Approach to Block Rewards.
Proceedings of the 1st ACM Conference on Advances in Financial Technologies, 2019

2018
Game dynamics as the meaning of a game.
SIGecom Exch., 2018

Towards a unified complexity theory of total functions.
J. Comput. Syst. Sci., 2018

From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory.
Entropy, 2018

The EATCS Award 2019 - Call for Nominations.
Bull. EATCS, 2018

Cycles in Adversarial Regularized Learning.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis.
Proceedings of the Robotics: Science and Systems XIV, 2018

Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Long Term Memory and the Densest K-Subgraph Problem.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

About Place Cells and Grid Cells - About Place Cells and Grid Cells.
Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017
The EATCS Award 2017 - Laudatio for Eva Tardos.
Bull. EATCS, 2017

TFNP: An Update.
Proceedings of the Algorithms and Complexity - 10th International Conference, 2017


2016
The Complexity of Fairness Through Equilibrium.
ACM Trans. Economics and Comput., 2016

Zero-Sum Polymatrix Games: A Generalization of Minmax.
Math. Oper. Res., 2016

On the optimality of grid cells.
CoRR, 2016

Sex as an algorithm: the theory of evolution under the lens of computation.
Commun. ACM, 2016

Power-Law Distributions in a Two-Sided Market and Net Neutrality.
Proceedings of the Web and Internet Economics - 12th International Conference, 2016

Computation as a Scientific Weltanschauung (Invited Talk).
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Does Information Revelation Improve Revenue?
Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Variable Binding through Assemblies in Spiking Neural Networks.
Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Information Processing Systems (NIPS 2016), 2016

On Satisfiability Problems with a Linear Structure.
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Optimizing the diamond lane: A more tractable carpool problem and algorithms.
Proceedings of the 19th IEEE International Conference on Intelligent Transportation Systems, 2016

On the Computational Complexity of Limit Cycles in Dynamical Systems.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Strategic Classification.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Can Almost Everybody be Almost Happy?
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Understanding evolution through algorithms.
Proceedings of the 2016 Formal Methods in Computer-Aided Design, 2016

Cortical Computation via Iterative Constructions.
Proceedings of the 29th Conference on Learning Theory, 2016

2015
Approximate Nash equilibria in anonymous games.
J. Econ. Theory, 2015

Optimal deterministic auctions with correlated priors.
Games Econ. Behav., 2015

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash.
CoRR, 2015

The Web Graph as an Equilibrium.
Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Cortical Computation.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Cortical Learning via Prediction.
Proceedings of The 28th Conference on Learning Theory, 2015

Optimum Statistical Estimation with Strategic Data Sources.
Proceedings of The 28th Conference on Learning Theory, 2015

On Neural Networks and Paul Spirakis.
Proceedings of the Algorithms, Probability, Networks, and Games, 2015

2014
Algorithms, games, and evolution.
Proc. Natl. Acad. Sci. USA, 2014

Unsupervised Learning through Prediction in a Model of Cortex.
CoRR, 2014

The Intractability of Dynamic Mechanism Design.
CoRR, 2014

Simultaneous bayesian auctions and computational complexity.
Proceedings of the ACM Conference on Economics and Computation, 2014

On Simplex Pivoting Rules and Complexity Theory.
Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Algorithms, Games, and Evolution (Invited Talk).
Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Satisfiability and Evolution.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions.
ACM Trans. Economics and Comput., 2013

Satisfiability and Evolution.
CoRR, 2013

Sparse Covers for Sums of Indicators.
CoRR, 2013

Learning and verifying quantified boolean queries by example.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Multiplicative updates in coordination games and the theory of evolution.
Proceedings of the Innovations in Theoretical Computer Science, 2013

2012
Alan and I.
Commun. ACM, 2012

The New Faces of Combinatorial Optimization.
Proceedings of the Combinatorial Optimization - Second International Symposium, 2012

Efficiency-Revenue Trade-Offs in Auctions.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

An Algorithmic View of the Universe.
Proceedings of the ACM Turing Centenary Celebration, 2012

2011
On the complexity of reconfiguration problems.
Theor. Comput. Sci., 2011

Games, algorithms, and the Internet.
Proceedings of the 20th International Conference on World Wide Web, 2011

Modeling Social Networks through User Background and Behavior.
Proceedings of the Algorithms and Models for the Web Graph - 8th International Workshop, 2011

On optimal single-item auctions.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Continuous Local Search.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Economies with non-convex production and complexity equilibria.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Mechanisms for complement-free procurement.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

2010
An impossibility theorem for price-adjustment mechanisms.
Proc. Natl. Acad. Sci. USA, 2010

Budget Feasible Mechanisms
CoRR, 2010

Inapproximability for VCG-Based Combinatorial Auctions.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

When the Players Are Not Expectation Maximizers.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

On Learning Algorithms for Nash Equilibria.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

A New Look at Selfish Routing.
Proceedings of the Innovations in Computer Science, 2010

2009
A note on approximate Nash equilibria.
Theor. Comput. Sci., 2009

Congestion games with malicious players.
Games Econ. Behav., 2009

Comparing Trade-off Based Models of the Internet.
Fundam. Informaticae, 2009

Worst-case equilibria.
Comput. Sci. Rev., 2009

VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension
CoRR, 2009

A Note on Strictly Competitive Games.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

On oblivious PTAS's for nash equilibrium.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

The ACM PODS Alberto O. Mendelzon test-of-time-award 2009.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

Algorithmic Game Theory: A Snapshot.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

On a Network Generalization of the Minmax Theorem.
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008
Computing correlated equilibria in multi-player games.
J. ACM, 2008

Market equilibrium via a primal-dual algorithm for a convex program.
J. ACM, 2008

Incentive-Compatible Interdomain Routing with Linear Utilities.
Internet Math., 2008

Some Recent Results in Algorithmic Game Theory.
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Linked decompositions of networks and the power of choice in Polya urns.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

The Search for Equilibrium Concepts.
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

On the Hardness of Being Truthful.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Algorithms.
McGraw-Hill, ISBN: 978-0-07-352340-8, 2008

2007
Approximately dominating representatives.
Theor. Comput. Sci., 2007

The Myth of the Folk Theorem.
Electron. Colloquium Comput. Complex., 2007

The Computation of Equilibria.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Progress in approximate nash equilibria.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Balancing traffic load in wireless networks with curveball routing.
Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2007

Computing Equilibria in Anonymous Games.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Nash Equilibria: Where We Stand.
Proceedings of the Algorithms, 2007

Computational complexity.
Academic Internet Publ., ISBN: 978-1-4288-1409-7, 2007

2006
Free-riding and whitewashing in peer-to-peer systems.
IEEE J. Sel. Areas Commun., 2006

On certain connectivity properties of the internet topology.
J. Comput. Syst. Sci., 2006

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.
Electron. Colloquium Comput. Complex., 2006

On The Approximability Of The Traveling Salesman Problem.
Comb., 2006

Recognizing Hole-Free 4-Map Graphs in Cubic Time.
Algorithmica, 2006

Computing pure nash equilibria in graphical games via markov random fields.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
On a conjecture related to geometric routing.
Theor. Comput. Sci., 2005

Three-Player Games Are Hard
Electron. Colloquium Comput. Complex., 2005

The complexity of computing a Nash equilibrium
Electron. Colloquium Comput. Complex., 2005

Reducibility Among Equilibrium Problems
Electron. Colloquium Comput. Complex., 2005

A BGP-based mechanism for lowest-cost routing.
Distributed Comput., 2005

An economic model of the worldwide web.
Proceedings of the 14th international conference on World Wide Web, 2005

Recent Developments in Equilibria Algorithms.
Proceedings of the Internet and Network Economics, First International Workshop, 2005

Experiments with an Economic Model of the Worldwide Web.
Proceedings of the Internet and Network Economics, First International Workshop, 2005

... The Interaction Between Algorithms and Game Theory.
Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

Computing correlated equilibria in multi-player games.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

The complexity of low-distortion embeddings between point sets.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Computing equilibria in multi-player games.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The Complexity of Games on Highly Regular Graphs.
Proceedings of the Algorithms, 2005

Algorithmic Problems in Ad Hoc Networks.
Proceedings of the Distributed Computing in Sensor Systems, 2005

Games Other People Play.
Proceedings of the CONCUR 2005 - Concurrency Theory, 16th International Conference, 2005

Approximating the Distortion.
Proceedings of the Approximation, 2005

Turing - a novel about computation.
MIT Press, ISBN: 978-0-262-66191-1, 2005

2004
Segmentation problems.
J. ACM, 2004

The complexity of pure Nash equilibria.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Selfish caching in distributed systems: a game-theoretic analysis.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Global Synchronization in Sensornets.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Networks and Games.
Proceedings of the High Performance Computing, 2004

2003
A simple algorithm for finding frequent elements in streams and bags.
ACM Trans. Database Syst., 2003

MythematiCS: in praise of storytelling in the teaching of computer science and math.
ACM SIGCSE Bull., 2003

Auditing Boolean attributes.
J. Comput. Syst. Sci., 2003

On the complexity of price equilibria.
J. Comput. Syst. Sci., 2003

An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents.
Internet Math., 2003

On the complexity of single-rule datalog queries.
Inf. Comput., 2003

On a network creation game.
Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, 2003

Geographic routing without location information.
Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking, 2003

<i>Mythematics</i>: storytelling in the teaching of computer science and mathematics.
Proceedings of the 8th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education, 2003

Games and Networks.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

The New Problems.
Proceedings of the PCK50, 2003

2002
A deterministic (2-2/(k+1))<sup>n</sup> algorithm for k-SAT based on local search.
Theor. Comput. Sci., 2002

Special Issue on PODS 1999 - Guest Editors' Foreword.
J. Comput. Syst. Sci., 2002

On a model of indexability and its bounds for range queries.
J. ACM, 2002

Map graphs.
J. ACM, 2002

The Joy of Theory.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

On the complexity of equilibria.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Selfish behavior and stability of the internet: a game-theoretic analysis of TCP.
Proceedings of the ACM SIGCOMM 2002 Conference on Applications, 2002

Understanding the Internet.
Proceedings of the Methods and Applications of Artificial Intelligence, 2002

On the Eigenvalue Power Law.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

The Internet, the Web, and Algorithms.
Proceedings of the LATIN 2002: Theoretical Informatics, 2002

Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Market Equilibrium via a Primal-Dual-Type Algorithm.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Learning the Internet.
Proceedings of the Computational Learning Theory, 2002

2001
Deciding stability and mortality of piecewise affine dynamical systems.
Theor. Comput. Sci., 2001

Sharing the Cost of Multicast Transmissions.
J. Comput. Syst. Sci., 2001

On Approximating a Scheduling Problem.
J. Comb. Optim., 2001

Game theory, algorithms, and the Internet.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Multiobjective Query Optimization.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Algorithms, Games, and the Internet.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Algorithmic problems related to the Internet.
Proceedings of the 5th Hellenic-European Conference on Computer Mathematics and its Applications (HERCMA-01), 2001

Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Reminiscences on Influential Papers.
SIGMOD Rec., 2000

Beyond Competitive Analysis.
SIAM J. Comput., 2000

On the Difficulty of Designing Good Classifiers.
SIAM J. Comput., 2000

Latent Semantic Indexing: A Probabilistic Analysis.
J. Comput. Syst. Sci., 2000

Distance-Based Reconstruction of Tree Models for Oncogenesis.
J. Comput. Biol., 2000

On the approximability of the traveling salesman problem (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Sharing the cost of muliticast transmissions (preliminary version).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

On certain rigorous approaches to data mining (invited talk, abstract only).
Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 2000

On the Approximability of Trade-offs and Optimal Access of Web Sources.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Optimization Problems in Congestion Control.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Theoretical Problems Related to the Internet.
Proceedings of the Computing and Combinatorics, 6th Annual International Conference, 2000

1999
Decision-making by hierarchies of discordant agents.
Math. Program., 1999

The Complexity of Optimal Queuing Network Control.
Math. Oper. Res., 1999

On the Floyd-Warshall Algorithm for Logic Programs.
J. Log. Program., 1999

Exploring an unknown graph.
J. Graph Theory, 1999

On the Complexity of Database Queries.
J. Comput. Syst. Sci., 1999

Topological Queries in Spatial Databases.
J. Comput. Syst. Sci., 1999

Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data.
J. Comput. Biol., 1999

Topological Queries.
Proceedings of the Advances in Spatial Databases, 1999

Novel Computational Approaches to Information Retrieval and Data Mining (Abstract).
Proceedings of the Database Theory, 1999

Algorithmic Aspects of Protein Structure Similarity.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Software Synthesis of Variable-length Code Decoder Using a Mixture of Programmed Logic and Table Lookups.
Proceedings of the Data Compression Conference, 1999

1998
Elements of the Theory of Computation.
SIGACT News, 1998

On the Complexity of Protein Folding.
J. Comput. Biol., 1998

Incremental Recompilation of Knowledge.
J. Artif. Intell. Res., 1998

How to Learn an Unknown Environment I: The Rectilinear Case.
J. ACM, 1998

Reflective Relational Machines.
Inf. Comput., 1998

A Microeconomic View of Data Mining.
Data Min. Knowl. Discov., 1998

On the Complexity of Protein Folding (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Planar Map Graphs.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On the complexity of protein folding (abstract).
Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

Algorithmic Approaches to Information Retrieval and Data Mining (Abstract).
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

Elements of the theory of computation, 2nd Edition.
Prentice Hall, ISBN: 978-0-13-262478-7, 1998

1997
Emerging opportunities for theoretical computer science.
SIGACT News, 1997

Tie-Breaking Semantics and Structural Totality.
J. Comput. Syst. Sci., 1997

On Kernels, Defaults and Even Graphs.
Ann. Math. Artif. Intell., 1997

Panarity, Revisited (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

On the Analysis of Indexing Schemes.
Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1997

NP-Completeness: A Retrospective.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Planar Topological Queries.
Proceedings of the Constraint Databases and Their Applications, 1997

1996
The future of computational complexity theory: part I.
SIGACT News, 1996

The Bisection Width of Grid Graphs.
Math. Syst. Theory, 1996

On Limited Nondeterminism and the Complexity of the V-C Dimension.
J. Comput. Syst. Sci., 1996

The 2-Evader Problem.
Inf. Process. Lett., 1996

Competitive Distributed Decision-Making.
Algorithmica, 1996

In Memoriam: Paris C. Kanellakis.
Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1996

Searching a Fixed Graph.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

Computational Aspacts of Organization Theory (Extended Abstract).
Proceedings of the Algorithms, 1996

The Complexity of Knowledge Representation.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
Reversible Simulation of Space-Bounded Computations.
Theor. Comput. Sci., 1995

Database metatheory: asking the big queries.
SIGACT News, 1995

On the k-Server Conjecture.
J. ACM, 1995

Multimedia Information Caching for Personalized Video-on-Demand.
Comput. Commun., 1995

Optimal Information Delivery.
Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

Topological Inference.
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995

The Comparative Linguistics of Knowledge Representation.
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995

An Approximation Scheme for Planar Graph TSP.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
The Complexity of Multiterminal Cuts.
SIAM J. Comput., 1994

On the Complexity of Cooperative Solution Concepts.
Math. Oper. Res., 1994

On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence.
J. Comput. Syst. Sci., 1994

Designing Secure Communication Protocols from Trust Specification.
Algorithmica, 1994

Default Theories that Always Have Extensions.
Artif. Intell., 1994

On complexity as bounded rationality (extended abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

The Power of Reflective Relational Machines
Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

Information Caching for Delivery of Personalized Video Programs on Home Entertainment Channels.
Proceedings of the International Conference on Multimedia Computing and Systems, 1994

Motion Planning on a Graph (Extended Abstract)
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

The Complexity of Optimal Queueing Network Control.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

On the Random Walk Method for Protocol Testing.
Proceedings of the Computer Aided Verification, 6th International Conference, 1994

Computational complexity.
Addison-Wesley, ISBN: 978-0-201-53082-7, 1994

1993
The Traveling Salesman Problem with Distances One and Two.
Math. Oper. Res., 1993

The Parallel Complexity of Simple Logic Programs.
J. ACM, 1993

Computing the Throughput of a Network with Dedicated Lines.
Discret. Appl. Math., 1993

Linear programming without the matrix.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On Horn Envelopes and Hypergraph Transversals.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract).
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem.
SIAM J. Comput., 1992

On the Greedy Algorithm for Satisfiability.
Inf. Process. Lett., 1992

On the Optimal Bisection of a Polygon.
INFORMS J. Comput., 1992

The Complexity of Multiway Cuts (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On Finding Extensions of Default Theories.
Proceedings of the Database Theory, 1992

1991
Shortest Paths Without a Map.
Theor. Comput. Sci., 1991

On Total Functions, Existence Theorems and Computational Complexity.
Theor. Comput. Sci., 1991

On path lengths modulo three.
J. Graph Theory, 1991

Optimization, Approximation, and Complexity Classes.
J. Comput. Syst. Sci., 1991

Why not Negation by Fixpoint?
J. Comput. Syst. Sci., 1991

The Weighted Region Problem: Finding Shortest Paths Through a Weighted Planar Subdivision.
J. ACM, 1991

Modularity of Cycles and Paths in Graphs.
J. ACM, 1991

On the Predictability of Coupled Automata: An Allegory about Chaos.
Complex Syst., 1991

On the Value of Information in Distributed Decision-Making (Extended Abstract).
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

Optimal Coteries.
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

Decision-Making with Incomplete Information.
Proceedings of the ISA '91 Algorithms, 1991

Designing Secure Communication Protocols from Trust Specifications.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

On Selecting a Satisfying Truth Assignment (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

How to Learn an Unknown Environment (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
Some Computational Aspects of Circumscription
J. ACM, January, 1990

Towards an Architecture-Independent Analysis of Parallel Algorithms.
SIAM J. Comput., 1990

The Optimum Execution Order of Queries in Linear Storage.
Inf. Process. Lett., 1990

The Geometry of Grasping.
Int. J. Robotics Res., 1990

On recognizing integer polyhedra.
Comb., 1990

A Linear Programming Approach to Reasoning about Probabilities.
Ann. Math. Artif. Intell., 1990

On the Complexity of Local Search (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Exploring an Unknown Graph (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On the Optimal Bisection of a Polygon (Extended Abstract).
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989
Corrigendum: The Complexity of Cubical Graphs
Inf. Comput., September, 1989

On the Convergence of Query Evaluation.
J. Comput. Syst. Sci., 1989

Exponential lower bounds for finding Brouwer fix points.
J. Complex., 1989

Finding Feasible Paths for a Two-Point Body.
J. Algorithms, 1989

Optimum Grip of a Polygon.
Int. J. Robotics Res., 1989

1988
Complexity Characterizations of Attribute Grammar Languages
Inf. Comput., September, 1988

The Complexity of Facets Resolved.
J. Comput. Syst. Sci., 1988

The Complexity of Recognizing Polyhedral Scenes.
J. Comput. Syst. Sci., 1988

How Easy is Local Search?
J. Comput. Syst. Sci., 1988

Probabilistic satisfiability.
J. Complex., 1988

The complexity of searching a graph.
J. ACM, 1988

On Generating All Maximal Independent Sets.
Inf. Process. Lett., 1988

The Synthesis of Communication Protocols.
Algorithmica, 1988

Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Optimization, Approximation, and Complexity Classes (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Scheduling Dags to Minimize Time and Communication.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
The Complexity of Reliable Concurrency Control.
SIAM J. Comput., 1987

A Communication-Time Tradeoff.
SIAM J. Comput., 1987

On Stochastic Scheduling with In-Tree Precedence Constraints.
SIAM J. Comput., 1987

The Discrete Geodesic Problem.
SIAM J. Comput., 1987

The Complexity of Markov Decision Processes.
Math. Oper. Res., 1987

The 1-Steiner Tree Problem.
J. Algorithms, 1987

Optimal Piecewise Linear Motion of an Object Among Obstacles.
Algorithmica, 1987

The Parallel Complexity of Simple Chain Queries.
Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1987

The Weighted Region Problem.
Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986
A Note on Succinct Representations of Graphs
Inf. Control., December, 1986

Searching and Pebbling.
Theor. Comput. Sci., 1986

Algorithmic Aspects of Multiversion Concurrency Control.
J. Comput. Syst. Sci., 1986

On the Complexity of Circulations.
J. Algorithms, 1986

The performance of a precedence-based queuing discipline.
J. ACM, 1986

The Complexity of the Travelling Repairman Problem.
RAIRO Theor. Informatics Appl., 1986

Convergence of Sideways Query Evaluation.
Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1986

Shortest-Path Motion.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

The Theory of Database Concurrency Control
Computer Science Press, ISBN: 0-88175-027-1, 1986

1985
Correction to "A Theorem in Database Concurrency Control"
J. ACM, July, 1985

The Complexity of Distributed Concurrency Control.
SIAM J. Comput., 1985

Games Against Nature.
J. Comput. Syst. Sci., 1985

An Algorithm for Shortest-Path Motion in Three Dimensions.
Inf. Process. Lett., 1985

The Complexity of Cubical Graphs
Inf. Control., 1985

A note the expressive power of Prolog.
Bull. EATCS, 1985

Interval graphs and seatching.
Discret. Math., 1985

The Complexity of Recognizing Polyhedral Scenes (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

How Easy Is Local Search? (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
On Concurrency Control by Multiple Versions.
ACM Trans. Database Syst., 1984

The Traveling Salesman Problem with Many Visits to Few Cities.
SIAM J. Comput., 1984

The even-path problem for graphs and digraphs.
Networks, 1984

The Complexity of Facets (and Some Facets of Complexity).
J. Comput. Syst. Sci., 1984

Communication Complexity.
J. Comput. Syst. Sci., 1984

Is Distributed Locking Harder?
J. Comput. Syst. Sci., 1984

Inclusion Dependencies and Their Interaction with Functional Dependencies.
J. Comput. Syst. Sci., 1984

On Two Geometric Problems Related to the Traveling Salesman Problem.
J. Algorithms, 1984

On the complexity of unique solutions.
J. ACM, 1984

Updates of Relational Views.
J. ACM, 1984

The Complexity of Cubical Graphs (Extended Abstract).
Proceedings of the Automata, 1984

1983
Concurrency Control by Locking.
SIAM J. Comput., 1983

An Optimality Theory of Concurrency Control for Databases.
Acta Informatica, 1983

Two remarks on the power of counting.
Proceedings of the Theoretical Computer Science, 1983

Theory of concurrency control.
Proceedings of the Theoretical Computer Science, 1983

Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract).
Proceedings of the Automata, 1983

Games Against Nature (Extended Abstract)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Topological Bandwidth.
Proceedings of the CAAP'83, 1983

1982
On the Complexity of Designing Distributed Protocols
Inf. Control., June, 1982

Symmetric Space-Bounded Computation.
Theor. Comput. Sci., 1982

On Linear Characterizations of Combinatorial Optimization Problems.
SIAM J. Comput., 1982

Hamilton Paths in Grid Graphs.
SIAM J. Comput., 1982

Algebraic Dependencies.
J. Comput. Syst. Sci., 1982

The complexity of restricted spanning tree problems.
J. ACM, 1982

A theorem in database concurrency control.
J. ACM, 1982

Combinatorial Optimization: Algorithms and Complexity
Prentice-Hall, ISBN: 0-13-152462-3, 1982

1981
Worst-Case and Probabilistic Analysis of a Geometric Location Problem.
SIAM J. Comput., 1981

Covering Graphs by Simple Circuits.
SIAM J. Comput., 1981

A Fast Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems.
J. Algorithms, 1981

On the complexity of integer programming.
J. ACM, 1981

The Clique Problem for Planar Graphs.
Inf. Process. Lett., 1981

On Minimal Eulerian Graphs.
Inf. Process. Lett., 1981

The Complexity of Testing Whether a Graph is a Superconcentrator.
Inf. Process. Lett., 1981

On the Power of Locking.
Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, Michigan, USA, April 29, 1981

Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

The Complexity of Searching a Graph (Preliminary Version)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

Elements of the Theory of Computation
Prentice-Hall, ISBN: 0-13-273426-5, 1981

1980
On the Performance of Balanced Hashing Functions When the Keys Are Not Equiprobable.
ACM Trans. Program. Lang. Syst., 1980

The Complexity of Coloring Circular Arcs and Chords.
SIAM J. Algebraic Discret. Methods, 1980

Flowshop scheduling with limited temporary storage.
J. ACM, 1980

Local Search for the Asymmetric Traveling Salesman Problem.
Oper. Res., 1980

A Worst-Case Analysis of Nearest Neighbor Searching by Projection.
Proceedings of the Automata, 1980

Symmetric Space-Bounded Computation (Extended Abstract).
Proceedings of the Automata, 1980

Algebraic Dependencies (Extended Abstract)
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979
Scheduling Interval-Ordered Tasks.
SIAM J. Comput., 1979

The serializability of concurrent database updates.
J. ACM, 1979

Optimality of the Fast Fourier transform.
J. ACM, 1979

Efficient Search for Rationals.
Inf. Process. Lett., 1979

Bounds for sorting by prefix reversal.
Discret. Math., 1979

The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract).
Proceedings of the Automata, 1979

Locking Policies: Safety and Freedom from Deadlock
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
The Concurrency Control Mechanism of SDD-1: A System for Distributed Databases (The Fully Redundant Case).
IEEE Trans. Software Eng., 1978

The complexity of the capacitated tree problem.
Networks, 1978

The adjacency relation on the traveling salesman polytope is NP-Complete.
Math. Program., 1978

Some Examples of Difficult Traveling Salesman Problems.
Oper. Res., 1978

1977
The Euclidean Traveling Salesman Problem is NP-Complete.
Theor. Comput. Sci., 1977

On the Complexity of Local Search for the Traveling Salesman Problem.
SIAM J. Comput., 1977

1976
On the complexity of edge traversing.
J. ACM, 1976

The NP-Completeness of the bandwidth minimization problem.
Computing, 1976

Some Complexity Results for the Traveling Salesman Problem
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976


  Loading...