Christos H. Papadimitriou

According to our database1, Christos H. Papadimitriou
  • authored at least 426 papers between 1976 and 2017.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Towards a Unified Complexity Theory of Total Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2017

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

Stathis Zachos at 70!
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

Cortical Computation via Iterative Constructions.
CoRR, 2016

On the optimality of grid cells.
CoRR, 2016

On Satisfiability Problems with a Linear Structure.
CoRR, 2016

Power-Law Distributions in a Two-sided Market and Net Neutrality.
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

On the Complexity of Dynamic Mechanism Design.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 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

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

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

Optimal deterministic auctions with correlated priors.
Games and Economic Behavior, 2015

On the Computational Complexity of Limit Cycles in Dynamical Systems.
CoRR, 2015

Strategic Classification.
CoRR, 2015

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.
CoRR, 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
Unsupervised Learning through Prediction in a Model of Cortex.
CoRR, 2014

The Intractability of Dynamic Mechanism Design.
CoRR, 2014

Optimum Statistical Estimation with Strategic Data Sources.
CoRR, 2014

On Simplex Pivoting Rules and Complexity Theory.
CoRR, 2014

The complexity of fairness through equilibrium.
Proceedings of the ACM Conference on Economics and Computation, 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

Learning and Verifying Quantified Boolean Queries by Example
CoRR, 2013

The Complexity of Fairness through Equilibrium.
CoRR, 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
Multiplicative Updates in Coordination Games and the Theory of Evolution
CoRR, 2012

Efficiency-Revenue Trade-offs in Auctions
CoRR, 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

On Oblivious PTAS's for Nash Equilibrium
CoRR, 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

The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
The myth of the Folk Theorem.
Games and Economic Behavior, 2010

On Optimal Single-Item Auctions
CoRR, 2010

The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
CoRR, 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

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.
SIAM J. Comput., 2009

The Complexity of Computing a Nash Equilibrium.
SIAM J. Comput., 2009

Congestion games with malicious players.
Games and Economic Behavior, 2009

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

Worst-case equilibria.
Computer Science Review, 2009

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

The complexity of computing a Nash equilibrium.
Commun. ACM, 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 Mathematics, 2008

Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games
CoRR, 2008

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

The myth of the folk theorem.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 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 Complexity of Reconfiguration Problems.
Proceedings of the Algorithms and Computation, 19th 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.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Computing Equilibria in Anonymous Games
CoRR, 2007

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

Incentive-Compatible Interdomain Routing with Linear Utilities.
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

Congestion games with malicious players.
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 Journal on Selected Areas in Communications, 2006

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

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.
Electronic Colloquium on Computational Complexity (ECCC), 2006

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
CoRR, 2006

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

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

A Note on Approximate Nash Equilibria.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Reducibility among equilibrium problems.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

The complexity of computing a Nash equilibrium.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 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 Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 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
Electronic Colloquium on Computational Complexity (ECCC), 2005

The complexity of computing a Nash equilibrium
Electronic Colloquium on Computational Complexity (ECCC), 2005

Reducibility Among Equilibrium Problems
Electronic Colloquium on Computational Complexity (ECCC), 2005

A BGP-based mechanism for lowest-cost routing.
Distributed Computing, 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

Approximately Dominating Representatives.
Proceedings of the Database Theory, 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

On a Conjecture Related to Geometric Routing.
Proceedings of the Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, 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.
SIGCSE Bulletin, 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 Mathematics, 2003

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

An approximate truthful mechanism for combinatorial auctions with single parameter agents.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Mythematics: 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

On Certain Connectivity Properties of the Internet Topology.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 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))n 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

A BGP-based mechanism for lowest-cost routing.
Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, 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

Algorithms, games, and the internet.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 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 Record, 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.
Journal of Computational Biology, 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

Auditing Boolean Attributes.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 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.
Journal of 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.
Journal of Computational Biology, 1999

Map Graphs
CoRR, 1999

Worst-case Equilibria.
Proceedings of the STACS 99, 1999

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

On the Complexity of Single-Rule Datalog Queries.
Proceedings of the Logic Programming and Automated Reasoning, 6th International Conference, 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.
Journal of Computational Biology, 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

Incremental Recompilation of Knowledge
CoRR, 1998

Segmentation Problems.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 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

Latent Semantic Indexing: A Probabilistic Analysis.
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 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 Complexity of Database Queries.
Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1997

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

Decision-Making by Hierarchies of Discordant Agents.
Proceedings of the Algorithms and Computation, 8th International Symposium, 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.
Mathematical Systems 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

Topological Queries in Spatial Databases.
Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 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

On the Difficulty of Designing Good Classifiers.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 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.
Computer Communications, 1995

Database Metatheory: Asking the Big Queries.
Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 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

Beyond Competitive Analysis
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

Incremental Recompilation of Knowledge.
Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31, 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.
Discrete Applied Mathematics, 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 Journal on Computing, 1992

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

Tie-Breaking Semantics and Structural Totality.
Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1992

Competitive Distributed Decision-Making.
Proceedings of the Algorithms, Software, Architecture, 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.
Journal of 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 Systems, 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.
I. J. Robotics Res., 1990

On recognizing integer polyhedra.
Combinatorica, 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

The Bisection Width of Grid Graphs.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 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 Predictability of Coupled Automata: An Allegory about Chaos
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. Complexity, 1989

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

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

Shortest Paths Without a Map.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 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. Complexity, 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

Why Not Negation by Fixpoint?
Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1988

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

Some Computational Aspects of Circumscription.
Proceedings of the 7th National Conference on Artificial Intelligence. St. Paul, 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

Complexity characterizations of attribute grammar languages.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986
A Note on Succinct Representations of Graphs
Information and 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.
ITA, 1986

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

The Synthesis of Communication Protocols.
Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 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
Information and Control, 1985

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

Interval graphs and seatching.
Discrete Mathematics, 1985

The Complexity of Reliable Concurrency Control.
Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1985

Algorithmic Aspects of Multiversion Concurrency Control.
Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1985

The Complexity of Facets Resolved
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 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

A Communication-Time Tradeoff
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

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

An Optimality Theory of Concurrency Control for Databases.
Acta Inf., 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

Updates of Relational Views.
Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 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
Information and 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

The Complexity of Facets (and Some Facets of Complexity)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Communication Complexity
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

On Concurrency Control by Multiple Versions.
Proceedings of the ACM Symposium on Principles of Database Systems, 1982

Is Distributed Locking Harder?
Proceedings of the ACM Symposium on Principles of Database Systems, 1982

Inclusion Dependencies and Their Interaction with Functional Dependencies.
Proceedings of the ACM Symposium on Principles of Database Systems, 1982

On the Complexity of Unique Solutions
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 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, 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

The Complexity of Distributed Concurrency Control
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. Matrix Analysis Applications, 1980

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

Local Search for the Asymmetric Traveling Salesman Problem.
Operations Research, 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

On Linear Characterizations of Combinatorial Optimization Problems
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.
Discrete Mathematics, 1979

An Optimality Theory of Concurrency Control for Databases.
Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, May 30, 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.
Operations Research, 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...