Christos H. Papadimitriou

Electron. Colloquium Comput. Complex., 2020

A New Age of Computing and the Brain.

[BibT_eX]

[DOI]

Stefan Schaal

Joshua T. Vogelstein

CoRR, 2020

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria.

[BibT_eX]

[DOI]

Kousha Etessami

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Brain Computation: A Computer Science Perspective.

[BibT_eX]

[DOI]

Robert Legenstein

Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019

Reductions in PPP.

[BibT_eX]

[DOI]

Frank Ban

Kamal Jain

Christos-Alexandros Psomas

Inf. Process. Lett., 2019

α-Rank: Multi-Agent Evaluation by Evolution.

[BibT_eX]

[DOI]

Shayegan Omidshafiei

Karl Tuyls

Mark Rowland

Jean-Baptiste Lespiau

Wojciech M. Czarnecki

Marc Lanctot

Julien Pérolat

Rémi Munos

CoRR, 2019

Wealth Inequality and the Price of Anarchy.

[BibT_eX]

[DOI]

Kurtulus Gemici

Barnabé Monnot

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Random Projection in the Brain and Computation with Assemblies of Neurons.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Energy Equilibria in Proof-of-Work Mining.

[BibT_eX]

[DOI]

Amos Fiat

Anna R. Karlin

Mohammad Taghi Hajiaghayi

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

Optimal Strategies of Blotto Games: Beyond Convexity.

[BibT_eX]

[DOI]

Soheil Behnezhad

Avrim Blum

Mahsa Derakhshan

Saeed Seddighin

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

An Axiomatic Approach to Block Rewards.

[BibT_eX]

[DOI]

Xi Chen

Tim Roughgarden

Proceedings of the 1st ACM Conference on Advances in Financial Technologies, 2019

2018

Game dynamics as the meaning of a game.

[BibT_eX]

[DOI]

SIGecom Exch., 2018

Towards a unified complexity theory of total functions.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

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

[BibT_eX]

[DOI]

Entropy, 2018

The EATCS Award 2019 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2018

Cycles in Adversarial Regularized Learning.

[BibT_eX]

[DOI]

Panayotis Mertikopoulos

Mohammad Taghi Hajiaghayi

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games.

[BibT_eX]

[DOI]

Soheil Behnezhad

Avrim Blum

Mahsa Derakhshan

Mohammad Mahdian

Ronald L. Rivest

Saeed Seddighin

Philip B. Stark

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.

[BibT_eX]

[DOI]

Maximilian Haas-Heger

Garud Iyengar

Matei T. Ciocarlie

Proceedings of the Robotics: Science and Systems XIV, 2018

Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons.

[BibT_eX]

[DOI]

Nima Anari

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.

[BibT_eX]

[DOI]

Robert Legenstein

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

About Place Cells and Grid Cells - About Place Cells and Grid Cells.

[BibT_eX]

[DOI]

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

The EATCS Award 2017 - Laudatio for Eva Tardos.

[BibT_eX]

[DOI]

Fedor V. Fomin

Jean-Eric Pin

Bull. EATCS, 2017

TFNP: An Update.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

Stathis Zachos at 70!

[BibT_eX]

[DOI]

Nikolaos S. Papaspyrou

Katerina Potika

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016

The Complexity of Fairness Through Equilibrium.

[BibT_eX]

[DOI]

Abraham Othman

ACM Trans. Economics and Comput., 2016

Zero-Sum Polymatrix Games: A Generalization of Minmax.

[BibT_eX]

[DOI]

Yang Cai

Ozan Candogan

Math. Oper. Res., 2016

On the optimality of grid cells.

[BibT_eX]

[DOI]

CoRR, 2016

Sex as an algorithm: the theory of evolution under the lens of computation.

[BibT_eX]

[DOI]

Commun. ACM, 2016

Power-Law Distributions in a Two-Sided Market and Net Neutrality.

[BibT_eX]

[DOI]

Zhe Feng

Proceedings of the Web and Internet Economics - 12th International Conference, 2016

Computation as a Scientific Weltanschauung (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.

[BibT_eX]

[DOI]

Ashwinkumar Badanidiyuru

Lior Seeman

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Does Information Revelation Improve Revenue?

[BibT_eX]

[DOI]

Christos Tzamos

Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Variable Binding through Assemblies in Spiking Neural Networks.

[BibT_eX]

[DOI]

Robert Legenstein

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.

[BibT_eX]

[DOI]

Serge Gaspers

Sigve Hortemo Sæther

Jan Arne Telle

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Optimizing the diamond lane: A more tractable carpool problem and algorithms.

[BibT_eX]

[DOI]

Cathy Wu

Kalyanaraman Shankari

Ece Kamar

Randy H. Katz

David E. Culler

Eric Horvitz

Alexandre M. Bayen

Proceedings of the 19th IEEE International Conference on Intelligent Transportation Systems, 2016

On the Computational Complexity of Limit Cycles in Dynamical Systems.

[BibT_eX]

[DOI]

Nisheeth K. Vishnoi

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

From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology.

[BibT_eX]

[DOI]

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

Strategic Classification.

[BibT_eX]

[DOI]

Moritz Hardt

Nimrod Megiddo

Mary Wootters

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

Can Almost Everybody be Almost Happy?

[BibT_eX]

[DOI]

Yakov Babichenko

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

Understanding evolution through algorithms.

[BibT_eX]

[DOI]

Proceedings of the 2016 Formal Methods in Computer-Aided Design, 2016

Cortical Computation via Iterative Constructions.

[BibT_eX]

[DOI]

Samantha Petti

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Approximate Nash equilibria in anonymous games.

[BibT_eX]

[DOI]

J. Econ. Theory, 2015

Optimal deterministic auctions with correlated priors.

[BibT_eX]

[DOI]

Games Econ. Behav., 2015

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

[BibT_eX]

[DOI]

Yakov Babichenko

CoRR, 2015

The Web Graph as an Equilibrium.

[BibT_eX]

[DOI]

Georgios Kouroupas

Evangelos Markakis

Vasileios Rigas

Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Cortical Computation.

[BibT_eX]

[DOI]

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Cortical Learning via Prediction.

[BibT_eX]

[DOI]

Proceedings of The 28th Conference on Learning Theory, 2015

Optimum Statistical Estimation with Strategic Data Sources.

[BibT_eX]

[DOI]

Yang Cai

Proceedings of The 28th Conference on Learning Theory, 2015

On Neural Networks and Paul Spirakis.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, Probability, Networks, and Games, 2015

2014

Algorithms, games, and evolution.

[BibT_eX]

[DOI]

Erick Chastain

Proc. Natl. Acad. Sci. USA, 2014

Unsupervised Learning through Prediction in a Model of Cortex.

[BibT_eX]

[DOI]

CoRR, 2014

The Intractability of Dynamic Mechanism Design.

[BibT_eX]

[DOI]

Christos-Alexandros Psomas

CoRR, 2014

Simultaneous bayesian auctions and computational complexity.

[BibT_eX]

[DOI]

Yang Cai

Proceedings of the ACM Conference on Economics and Computation, 2014

On Simplex Pivoting Rules and Complexity Theory.

[BibT_eX]

[DOI]

Ilan Adler

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Algorithms, Games, and Evolution (Invited Talk).

[BibT_eX]

[DOI]

Erick Chastain

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Satisfiability and Evolution.

[BibT_eX]

[DOI]

Gregory Valiant

Andrew Wan

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.

[BibT_eX]

[DOI]

Rahul Savani

ACM Trans. Economics and Comput., 2013

Satisfiability and Evolution.

[BibT_eX]

[DOI]

Andrew Wan

CoRR, 2013

Sparse Covers for Sums of Indicators.

[BibT_eX]

[DOI]

CoRR, 2013

Learning and verifying quantified boolean queries by example.

[BibT_eX]

[DOI]

Azza Abouzied

Dana Angluin

Joseph M. Hellerstein

Avi Silberschatz

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.

[BibT_eX]

[DOI]

Erick Chastain

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Alan and I.

[BibT_eX]

[DOI]

Commun. ACM, 2012

The New Faces of Combinatorial Optimization.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization - Second International Symposium, 2012

Efficiency-Revenue Trade-Offs in Auctions.

[BibT_eX]

[DOI]

Ilias Diakonikolas

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

An Algorithmic View of the Universe.

[BibT_eX]

[DOI]

Proceedings of the ACM Turing Centenary Celebration, 2012

2011

On the complexity of reconfiguration problems.

[BibT_eX]

[DOI]

Takehiro Ito

Erik D. Demaine

Nicholas J. A. Harvey

Ryuhei Uehara

Yushi Uno

Theor. Comput. Sci., 2011

Games, algorithms, and the Internet.

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on World Wide Web, 2011

Modeling Social Networks through User Background and Behavior.

[BibT_eX]

[DOI]

Ilias Foudalis

Kamal Jain

Proceedings of the Algorithms and Models for the Web Graph - 8th International Workshop, 2011

On optimal single-item auctions.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Continuous Local Search.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Economies with non-convex production and complexity equilibria.

[BibT_eX]

[DOI]

Christopher A. Wilkens

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Mechanisms for complement-free procurement.

[BibT_eX]

[DOI]

Shahar Dobzinski

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

2010

An impossibility theorem for price-adjustment mechanisms.

[BibT_eX]

[DOI]

Proc. Natl. Acad. Sci. USA, 2010

Budget Feasible Mechanisms

[BibT_eX]

[DOI]

CoRR, 2010

Inapproximability for VCG-Based Combinatorial Auctions.

[BibT_eX]

[DOI]

Michael Schapira

Christopher Umans

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

When the Players Are Not Expectation Maximizers.

[BibT_eX]

[DOI]

Amos Fiat

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

On Learning Algorithms for Nash Equilibria.

[BibT_eX]

[DOI]

Rafael M. Frongillo

Gregory Valiant

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

A New Look at Selfish Routing.

[BibT_eX]

[DOI]

Gregory Valiant

Proceedings of the Innovations in Computer Science, 2010

2009

A note on approximate Nash equilibria.

[BibT_eX]

[DOI]

Aranyak Mehta

Theor. Comput. Sci., 2009

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.

[BibT_eX]

[DOI]

Parikshit Gopalan

Elitza N. Maneva

SIAM J. Comput., 2009

The Complexity of Computing a Nash Equilibrium.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Congestion games with malicious players.

[BibT_eX]

[DOI]

Moshe Babaioff

Robert Kleinberg

Games Econ. Behav., 2009

Comparing Trade-off Based Models of the Internet.

[BibT_eX]

[DOI]

Anthony Spatharis

Ilias Foudalis

Fundam. Informaticae, 2009

Worst-case equilibria.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2009

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

[BibT_eX]

[DOI]

Elchanan Mossel

Michael Schapira

CoRR, 2009

A Note on Strictly Competitive Games.

[BibT_eX]

[DOI]

Ilan Adler

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

On oblivious PTAS's for nash equilibrium.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

The ACM PODS Alberto O. Mendelzon test-of-time-award 2009.

[BibT_eX]

[DOI]

Catriel Beeri

Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

Algorithmic Game Theory: A Snapshot.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

On a Network Generalization of the Minmax Theorem.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008

Computing correlated equilibria in multi-player games.

[BibT_eX]

[DOI]

Tim Roughgarden

J. ACM, 2008

Market equilibrium via a primal-dual algorithm for a convex program.

[BibT_eX]

[DOI]

Nikhil R. Devanur

Vijay V. Vazirani

J. ACM, 2008

Incentive-Compatible Interdomain Routing with Linear Utilities.

[BibT_eX]

[DOI]

Alexander Hall

Evdokia Nikolova

Internet Math., 2008

Some Recent Results in Algorithmic Game Theory.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Linked decompositions of networks and the power of choice in Polya urns.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

The Search for Equilibrium Concepts.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

On the Hardness of Being Truthful.

[BibT_eX]

[DOI]

Michael Schapira

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Algorithms.

[BibT_eX]

Sanjoy Dasgupta

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

2007

Approximately dominating representatives.

[BibT_eX]

[DOI]

Vladlen Koltun

Theor. Comput. Sci., 2007

The Myth of the Folk Theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

The Computation of Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Progress in approximate nash equilibria.

[BibT_eX]

[DOI]

Aranyak Mehta

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Balancing traffic load in wireless networks with curveball routing.

[BibT_eX]

[DOI]

Lucian Popa

Afshin Rostamizadeh

Ion Stoica

Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2007

Computing Equilibria in Anonymous Games.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Nash Equilibria: Where We Stand.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2007

Computational complexity.

[BibT_eX]

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

2006

Free-riding and whitewashing in peer-to-peer systems.

[BibT_eX]

[DOI]

Michal Feldman

John Chuang

Ion Stoica

IEEE J. Sel. Areas Commun., 2006

On certain connectivity properties of the internet topology.

[BibT_eX]

[DOI]

Milena Mihail

J. Comput. Syst. Sci., 2006

On The Approximability Of The Traveling Salesman Problem.

[BibT_eX]

[DOI]

Comb., 2006

Recognizing Hole-Free 4-Map Graphs in Cubic Time.

[BibT_eX]

[DOI]

Algorithmica, 2006

Computing pure nash equilibria in graphical games via markov random fields.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

On a conjecture related to geometric routing.

[BibT_eX]

[DOI]

David Ratajczak

Theor. Comput. Sci., 2005

Three-Player Games Are Hard

[BibT_eX]

[DOI]

Konstantinos Daskalakis

Electron. Colloquium Comput. Complex., 2005

Reducibility Among Equilibrium Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

A BGP-based mechanism for lowest-cost routing.

[BibT_eX]

[DOI]

Joan Feigenbaum

Rahul Sami

Distributed Comput., 2005

An economic model of the worldwide web.

[BibT_eX]

[DOI]

Georgios Kouroupas

Proceedings of the 14th international conference on World Wide Web, 2005

Recent Developments in Equilibria Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, First International Workshop, 2005

Experiments with an Economic Model of the Worldwide Web.

[BibT_eX]

[DOI]

Georgios Kouroupas

Proceedings of the Internet and Network Economics, First International Workshop, 2005

... The Interaction Between Algorithms and Game Theory.

[BibT_eX]

[DOI]

Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

Computing correlated equilibria in multi-player games.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

The complexity of low-distortion embeddings between point sets.

[BibT_eX]

[DOI]

Shmuel Safra

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Computing equilibria in multi-player games.

[BibT_eX]

[DOI]

Tim Roughgarden

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The Complexity of Games on Highly Regular Graphs.

[BibT_eX]

[DOI]

Konstantinos Daskalakis

Proceedings of the Algorithms, 2005

Algorithmic Problems in Ad Hoc Networks.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing in Sensor Systems, 2005

Games Other People Play.

[BibT_eX]

[DOI]

Proceedings of the CONCUR 2005 - Concurrency Theory, 16th International Conference, 2005

Approximating the Distortion.

[BibT_eX]

[DOI]

Alexander Hall

Proceedings of the Approximation, 2005

Turing - a novel about computation.

[BibT_eX]

MIT Press, ISBN: 978-0-262-66191-1, 2005

2004

Segmentation problems.

[BibT_eX]

[DOI]

Jon M. Kleinberg

J. ACM, 2004

The complexity of pure Nash equilibria.

[BibT_eX]

[DOI]

Kunal Talwar

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Selfish caching in distributed systems: a game-theoretic analysis.

[BibT_eX]

[DOI]

John Kubiatowicz

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Global Synchronization in Sensornets.

[BibT_eX]

[DOI]

Jeremy Elson

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Networks and Games.

[BibT_eX]

[DOI]

Proceedings of the High Performance Computing, 2004

2003

A simple algorithm for finding frequent elements in streams and bags.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2003

MythematiCS: in praise of storytelling in the teaching of computer science and math.

[BibT_eX]

[DOI]

ACM SIGCSE Bull., 2003

Auditing Boolean attributes.

[BibT_eX]

[DOI]

Jon M. Kleinberg

J. Comput. Syst. Sci., 2003

On the complexity of price equilibria.

[BibT_eX]

[DOI]

Shmuel Safra

J. Comput. Syst. Sci., 2003

An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents.

[BibT_eX]

[DOI]

Aaron Archer

Kunal Talwar

Éva Tardos

Internet Math., 2003

On the complexity of single-rule datalog queries.

[BibT_eX]

[DOI]

Georg Gottlob

Inf. Comput., 2003

On a network creation game.

[BibT_eX]

[DOI]

Ankur Luthra

Elitza N. Maneva

Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, 2003

Geographic routing without location information.

[BibT_eX]

[DOI]

Ananth Rao

Ion Stoica

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.

[BibT_eX]

[DOI]

Proceedings of the 8th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education, 2003

Games and Networks.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

The New Problems.

[BibT_eX]

[DOI]

Proceedings of the PCK50, 2003

2002

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

[BibT_eX]

[DOI]

Uwe Schöning

Theor. Comput. Sci., 2002

Special Issue on PODS 1999 - Guest Editors' Foreword.

[BibT_eX]

[DOI]

Yannis E. Ioannidis

J. Comput. Syst. Sci., 2002

On a model of indexability and its bounds for range queries.

[BibT_eX]

[DOI]

Joseph M. Hellerstein

Daniel P. Miranker

Vasilis Samoladas

J. ACM, 2002

Map graphs.

[BibT_eX]

[DOI]

J. ACM, 2002

The Joy of Theory.

[BibT_eX]

[DOI]

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

On the complexity of equilibria.

[BibT_eX]

[DOI]

Shmuel Safra

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.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGCOMM 2002 Conference on Applications, 2002

Understanding the Internet.

[BibT_eX]

[DOI]

Proceedings of the Methods and Applications of Artificial Intelligence, 2002

On the Eigenvalue Power Law.

[BibT_eX]

[DOI]

Milena Mihail

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

The Internet, the Web, and Algorithms.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Market Equilibrium via a Primal-Dual-Type Algorithm.

[BibT_eX]

[DOI]

Nikhil R. Devanur

Vijay V. Vazirani

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Learning the Internet.

[BibT_eX]

[DOI]

Proceedings of the Computational Learning Theory, 2002

2001

Deciding stability and mortality of piecewise affine dynamical systems.

[BibT_eX]

[DOI]

Vincent D. Blondel

Olivier Bournez

Pascal Koiran

Theor. Comput. Sci., 2001

Sharing the Cost of Multicast Transmissions.

[BibT_eX]

[DOI]

Joan Feigenbaum

J. Comput. Syst. Sci., 2001

On Approximating a Scheduling Problem.

[BibT_eX]

[DOI]

J. Comb. Optim., 2001

Algorithms, games, and the internet.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Game theory, algorithms, and the Internet.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Multiobjective Query Optimization.

[BibT_eX]

[DOI]

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

Algorithmic problems related to the Internet.

[BibT_eX]

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.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Reminiscences on Influential Papers.

[BibT_eX]

[DOI]

Kenneth A. Ross

Yannis E. Ioannidis

Anant Jhingran

SIGMOD Rec., 2000

Beyond Competitive Analysis.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

On the Difficulty of Designing Good Classifiers.

[BibT_eX]

[DOI]

Vincent Mirelli

SIAM J. Comput., 2000

Latent Semantic Indexing: A Probabilistic Analysis.

[BibT_eX]

[DOI]

Hisao Tamaki

J. Comput. Syst. Sci., 2000

Distance-Based Reconstruction of Tree Models for Oncogenesis.

[BibT_eX]

[DOI]

Alejandro A. Schäffer

J. Comput. Biol., 2000

On the approximability of the traveling salesman problem (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Sharing the cost of muliticast transmissions (preliminary version).

[BibT_eX]

[DOI]

Joan Feigenbaum

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

On certain rigorous approaches to data mining (invited talk, abstract only).

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Optimization Problems in Congestion Control.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Theoretical Problems Related to the Internet.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 6th Annual International Conference, 2000

1999

Decision-making by hierarchies of discordant agents.

[BibT_eX]

[DOI]

Math. Program., 1999

The Complexity of Optimal Queuing Network Control.

[BibT_eX]

[DOI]

Math. Oper. Res., 1999

On the Floyd-Warshall Algorithm for Logic Programs.

[BibT_eX]

[DOI]

J. Log. Program., 1999

Exploring an unknown graph.

[BibT_eX]

[DOI]

J. Graph Theory, 1999

On the Complexity of Database Queries.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

Topological Queries in Spatial Databases.

[BibT_eX]

[DOI]

Dan Suciu

Victor Vianu

J. Comput. Syst. Sci., 1999

Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data.

[BibT_eX]

[DOI]

Alejandro A. Schäffer

J. Comput. Biol., 1999

Topological Queries.

[BibT_eX]

[DOI]

Proceedings of the Advances in Spatial Databases, 1999

Novel Computational Approaches to Information Retrieval and Data Mining (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Database Theory, 1999

Algorithmic Aspects of Protein Structure Similarity.

[BibT_eX]

[DOI]

Sorin Istrail

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.

[BibT_eX]

[DOI]

Gene Cheung

Steven McCanne

Proceedings of the Data Compression Conference, 1999

1998

Elements of the Theory of Computation.

[BibT_eX]

[DOI]

SIGACT News, 1998

On the Complexity of Protein Folding.

[BibT_eX]

[DOI]

Antonio Piccolboni

J. Comput. Biol., 1998

Incremental Recompilation of Knowledge.

[BibT_eX]

[DOI]

Goran Gogic

J. Artif. Intell. Res., 1998

How to Learn an Unknown Environment I: The Rectilinear Case.

[BibT_eX]

[DOI]

Tiko Kameda

J. ACM, 1998

Reflective Relational Machines.

[BibT_eX]

[DOI]

Serge Abiteboul

Victor Vianu

Inf. Comput., 1998

A Microeconomic View of Data Mining.

[BibT_eX]

[DOI]

Jon M. Kleinberg

Data Min. Knowl. Discov., 1998

On the Complexity of Protein Folding (Extended Abstract).

[BibT_eX]

[DOI]

Antonio Piccolboni

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Planar Map Graphs.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On the complexity of protein folding (abstract).

[BibT_eX]

[DOI]

Antonio Piccolboni

Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

Algorithmic Approaches to Information Retrieval and Data Mining (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

Elements of the theory of computation, 2nd Edition.

[BibT_eX]

Prentice Hall, ISBN: 978-0-13-262478-7, 1998

1997

Emerging opportunities for theoretical computer science.

[BibT_eX]

[DOI]

Pavel A. Pevzner

SIGACT News, 1997

Tie-Breaking Semantics and Structural Totality.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1997

On Kernels, Defaults and Even Graphs.

[BibT_eX]

[DOI]

Yannis Dimopoulos

Vangelis Magirou

Ann. Math. Artif. Intell., 1997

Panarity, Revisited (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

On the Analysis of Indexing Schemes.

[BibT_eX]

[DOI]

Joseph M. Hellerstein

Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1997

NP-Completeness: A Retrospective.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Planar Topological Queries.

[BibT_eX]

[DOI]

Proceedings of the Constraint Databases and Their Applications, 1997

1996

The future of computational complexity theory: part I.

[BibT_eX]

[DOI]

Oded Goldreich

Avi Wigderson

Alexander A. Razborov

Michael Sipser

SIGACT News, 1996

The Bisection Width of Grid Graphs.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1996

On Limited Nondeterminism and the Complexity of the V-C Dimension.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

The 2-Evader Problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1996

Competitive Distributed Decision-Making.

[BibT_eX]

[DOI]

Algorithmica, 1996

In Memoriam: Paris C. Kanellakis.

[BibT_eX]

[DOI]

Serge Abiteboul

Gabriel M. Kuper

Moshe Y. Vardi

Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1996

Searching a Fixed Graph.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

Computational Aspacts of Organization Theory (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1996

The Complexity of Knowledge Representation.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Reversible Simulation of Space-Bounded Computations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

Database metatheory: asking the big queries.

[BibT_eX]

[DOI]

SIGACT News, 1995

On the k-Server Conjecture.

[BibT_eX]

[DOI]

J. ACM, 1995

Multimedia Information Caching for Personalized Video-on-Demand.

[BibT_eX]

Srinivas Ramanathan

Srihari Sampath Kumar

Comput. Commun., 1995

Optimal Information Delivery.

[BibT_eX]

[DOI]

Srinivas Ramanathan

Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

Topological Inference.

[BibT_eX]

[DOI]

Dimitris Papadias

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

The Comparative Linguistics of Knowledge Representation.

[BibT_eX]

[DOI]

Goran Gogic

Henry A. Kautz

Bart Selman

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

An Approximation Scheme for Planar Graph TSP.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

The Complexity of Multiterminal Cuts.

[BibT_eX]

[DOI]

Elias Dahlhaus

Paul D. Seymour

SIAM J. Comput., 1994

On the Complexity of Cooperative Solution Concepts.

[BibT_eX]

[DOI]

Math. Oper. Res., 1994

On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

Designing Secure Communication Protocols from Trust Specification.

[BibT_eX]

[DOI]

Algorithmica, 1994

Default Theories that Always Have Extensions.

[BibT_eX]

[DOI]

Artif. Intell., 1994

On complexity as bounded rationality (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

The Power of Reflective Relational Machines

[BibT_eX]

[DOI]

Serge Abiteboul

Victor Vianu

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.

[BibT_eX]

[DOI]

Srinivas Ramanathan

Proceedings of the International Conference on Multimedia Computing and Systems, 1994

Motion Planning on a Graph (Extended Abstract)

[BibT_eX]

[DOI]

Madhu Sudan

Hisao Tamaki

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

The Complexity of Optimal Queueing Network Control.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

On the Random Walk Method for Protocol Testing.

[BibT_eX]

[DOI]

Milena Mihail

Proceedings of the Computer Aided Verification, 6th International Conference, 1994

Computational complexity.

[BibT_eX]

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

1993

The Traveling Salesman Problem with Distances One and Two.

[BibT_eX]

[DOI]

Math. Oper. Res., 1993

The Parallel Complexity of Simple Logic Programs.

[BibT_eX]

[DOI]

J. ACM, 1993

Computing the Throughput of a Network with Dedicated Lines.

[BibT_eX]

[DOI]

Paolo Serafini

Discret. Appl. Math., 1993

Linear programming without the matrix.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On Horn Envelopes and Hypergraph Transversals.

[BibT_eX]

[DOI]

Dimitris J. Kavvadias

Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

The Complexity of the Lin-Kernighan Heuristic for the Traveling Salesman Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1992

On the Greedy Algorithm for Satisfiability.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

On the Optimal Bisection of a Polygon.

[BibT_eX]

[DOI]

INFORMS J. Comput., 1992

The Complexity of Multiway Cuts (Extended Abstract)

[BibT_eX]

[DOI]

Elias Dahlhaus

Paul D. Seymour

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On Finding Extensions of Default Theories.

[BibT_eX]

[DOI]

Proceedings of the Database Theory, 1992

1991

Shortest Paths Without a Map.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

On Total Functions, Existence Theorems and Computational Complexity.

[BibT_eX]

[DOI]

Nimrod Megiddo

Theor. Comput. Sci., 1991

On path lengths modulo three.

[BibT_eX]

[DOI]

J. Graph Theory, 1991

Optimization, Approximation, and Complexity Classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

Why not Negation by Fixpoint?

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

The Weighted Region Problem: Finding Shortest Paths Through a Weighted Planar Subdivision.

[BibT_eX]

[DOI]

Joseph S. B. Mitchell

J. ACM, 1991

Modularity of Cycles and Paths in Graphs.

[BibT_eX]

[DOI]

Esther M. Arkin

J. ACM, 1991

On the Predictability of Coupled Automata: An Allegory about Chaos.

[BibT_eX]

[DOI]

Samuel R. Buss

Complex Syst., 1991

On the Value of Information in Distributed Decision-Making (Extended Abstract).

[BibT_eX]

[DOI]

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

Optimal Coteries.

[BibT_eX]

[DOI]

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

Decision-Making with Incomplete Information.

[BibT_eX]

[DOI]

Proceedings of the ISA '91 Algorithms, 1991

Designing Secure Communication Protocols from Trust Specifications.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

On Selecting a Satisfying Truth Assignment (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

How to Learn an Unknown Environment (Extended Abstract)

[BibT_eX]

[DOI]

Tiko Kameda

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Some Computational Aspects of Circumscription

[BibT_eX]

[DOI]

J. ACM, January, 1990

Towards an Architecture-Independent Analysis of Parallel Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

The Optimum Execution Order of Queries in Linear Storage.

[BibT_eX]

[DOI]

John G. Kollias

Yannis Manolopoulos

Inf. Process. Lett., 1990

The Geometry of Grasping.

[BibT_eX]

[DOI]

Xanthippi Markenscoff

Luqun Ni

Int. J. Robotics Res., 1990

On recognizing integer polyhedra.

[BibT_eX]

[DOI]

Comb., 1990

A Linear Programming Approach to Reasoning about Probabilities.

[BibT_eX]

[DOI]

Dimitris J. Kavvadias

Ann. Math. Artif. Intell., 1990

On the Complexity of Local Search (Extended Abstract)

[BibT_eX]

[DOI]

Alejandro A. Schäffer

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Exploring an Unknown Graph (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On the Optimal Bisection of a Polygon (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989

Corrigendum: The Complexity of Cubical Graphs

[BibT_eX]

[DOI]

Inf. Comput., September, 1989

On the Convergence of Query Evaluation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1989

Exponential lower bounds for finding Brouwer fix points.

[BibT_eX]

[DOI]

Michael D. Hirsch

Stephen A. Vavasis

J. Complex., 1989

Finding Feasible Paths for a Two-Point Body.

[BibT_eX]

[DOI]

Ellen B. Feinberg

J. Algorithms, 1989

Optimum Grip of a Polygon.

[BibT_eX]

[DOI]

Xanthippi Markenscoff

Int. J. Robotics Res., 1989

1988

Complexity Characterizations of Attribute Grammar Languages

[BibT_eX]

[DOI]

Sophocles Ephremidis

Inf. Comput., September, 1988

The Complexity of Facets Resolved.

[BibT_eX]

[DOI]

David Wolfe

J. Comput. Syst. Sci., 1988

The Complexity of Recognizing Polyhedral Scenes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1988

How Easy is Local Search?

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1988

Probabilistic satisfiability.

[BibT_eX]

[DOI]

George F. Georgakopoulos

Dimitris J. Kavvadias

J. Complex., 1988

The complexity of searching a graph.

[BibT_eX]

[DOI]

J. ACM, 1988

On Generating All Maximal Independent Sets.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

The Synthesis of Communication Protocols.

[BibT_eX]

[DOI]

Algorithmica, 1988

Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Optimization, Approximation, and Complexity Classes (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Scheduling Dags to Minimize Time and Communication.

[BibT_eX]

[DOI]

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987

The Complexity of Reliable Concurrency Control.

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

A Communication-Time Tradeoff.

[BibT_eX]

[DOI]

Jeffrey D. Ullman

SIAM J. Comput., 1987

On Stochastic Scheduling with In-Tree Precedence Constraints.

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

The Discrete Geodesic Problem.

[BibT_eX]

[DOI]

Joseph S. B. Mitchell

David M. Mount

SIAM J. Comput., 1987

The Complexity of Markov Decision Processes.

[BibT_eX]

[DOI]

Math. Oper. Res., 1987

The 1-Steiner Tree Problem.

[BibT_eX]

[DOI]

George K. Georgakopoulos

J. Algorithms, 1987

Optimal Piecewise Linear Motion of an Object Among Obstacles.

[BibT_eX]

[DOI]

Ellen B. Silverberg

Algorithmica, 1987

The Parallel Complexity of Simple Chain Queries.

[BibT_eX]

[DOI]

Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1987

The Weighted Region Problem.

[BibT_eX]

[DOI]

Joseph S. B. Mitchell

Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986

A Note on Succinct Representations of Graphs

[BibT_eX]

[DOI]

Inf. Control., December, 1986

Searching and Pebbling.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

Algorithmic Aspects of Multiversion Concurrency Control.

[BibT_eX]

[DOI]

Thanasis Hadzilacos

J. Comput. Syst. Sci., 1986

On the Complexity of Circulations.

[BibT_eX]

[DOI]

Esther M. Arkin

J. Algorithms, 1986

The performance of a precedence-based queuing discipline.

[BibT_eX]

[DOI]

Pierre A. Humblet

J. ACM, 1986

The Complexity of the Travelling Repairman Problem.

[BibT_eX]

[DOI]

Nadia Papakostantinou

RAIRO Theor. Informatics Appl., 1986

Convergence of Sideways Query Evaluation.

[BibT_eX]

[DOI]

Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1986

Shortest-Path Motion.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

The Theory of Database Concurrency Control

[BibT_eX]

Computer Science Press, ISBN: 0-88175-027-1, 1986

1985

Correction to "A Theorem in Database Concurrency Control"

[BibT_eX]

J. ACM, July, 1985

The Complexity of Distributed Concurrency Control.

[BibT_eX]

[DOI]

SIAM J. Comput., 1985

Games Against Nature.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1985

An Algorithm for Shortest-Path Motion in Three Dimensions.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1985

The Complexity of Cubical Graphs

[BibT_eX]

[DOI]

Inf. Control., 1985

A note the expressive power of Prolog.

[BibT_eX]

Bull. EATCS, 1985

Interval graphs and seatching.

[BibT_eX]

[DOI]

Discret. Math., 1985

The Complexity of Recognizing Polyhedral Scenes (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

How Easy Is Local Search? (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

On Concurrency Control by Multiple Versions.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 1984

The Traveling Salesman Problem with Many Visits to Few Cities.

[BibT_eX]

[DOI]

SIAM J. Comput., 1984

The even-path problem for graphs and digraphs.

[BibT_eX]

[DOI]

Andrea S. LaPaugh

Networks, 1984

The Complexity of Facets (and Some Facets of Complexity).

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1984

Communication Complexity.

[BibT_eX]

[DOI]

Michael Sipser

J. Comput. Syst. Sci., 1984

Is Distributed Locking Harder?

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1984

Inclusion Dependencies and Their Interaction with Functional Dependencies.

[BibT_eX]

[DOI]

Marco A. Casanova

Ronald Fagin

J. Comput. Syst. Sci., 1984

On Two Geometric Problems Related to the Traveling Salesman Problem.

[BibT_eX]

[DOI]

J. Algorithms, 1984

On the complexity of unique solutions.

[BibT_eX]

[DOI]

J. ACM, 1984

Updates of Relational Views.

[BibT_eX]

[DOI]

J. ACM, 1984

The Complexity of Cubical Graphs (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1984

1983

Concurrency Control by Locking.

[BibT_eX]

[DOI]

SIAM J. Comput., 1983

An Optimality Theory of Concurrency Control for Databases.

[BibT_eX]

[DOI]

H. T. Kung

Acta Informatica, 1983

Two remarks on the power of counting.

[BibT_eX]

[DOI]

Stathis Zachos

Proceedings of the Theoretical Computer Science, 1983

Theory of concurrency control.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 1983

Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1983

Games Against Nature (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Topological Bandwidth.

[BibT_eX]

[DOI]

Fillia Makedon

Ivan Hal Sudborough

Proceedings of the CAAP'83, 1983

1982

On the Complexity of Designing Distributed Protocols

[BibT_eX]

[DOI]

Inf. Control., June, 1982

Symmetric Space-Bounded Computation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

On Linear Characterizations of Combinatorial Optimization Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1982

Hamilton Paths in Grid Graphs.

[BibT_eX]

[DOI]

Alon Itai

Jayme Luiz Szwarcfiter

SIAM J. Comput., 1982

Algebraic Dependencies.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1982

The complexity of restricted spanning tree problems.

[BibT_eX]

[DOI]

J. ACM, 1982

A theorem in database concurrency control.

[BibT_eX]

[DOI]

J. ACM, 1982

Combinatorial Optimization: Algorithms and Complexity

[BibT_eX]

Prentice-Hall, ISBN: 0-13-152462-3, 1982

1981

Worst-Case and Probabilistic Analysis of a Geometric Location Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1981

Covering Graphs by Simple Circuits.

[BibT_eX]

[DOI]

Alon Itai

Richard J. Lipton

Michael Rodeh

SIAM J. Comput., 1981

A Fast Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems.

[BibT_eX]

[DOI]

Witold Lipski Jr.

J. Algorithms, 1981

On the complexity of integer programming.

[BibT_eX]

[DOI]

J. ACM, 1981

The Clique Problem for Planar Graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1981

On Minimal Eulerian Graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1981

The Complexity of Testing Whether a Graph is a Superconcentrator.

[BibT_eX]

[DOI]

Manuel Blum

Oliver Vornberger

Inf. Process. Lett., 1981

On the Power of Locking.

[BibT_eX]

[DOI]

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)

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

The Complexity of Searching a Graph (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

Elements of the Theory of Computation

[BibT_eX]

[DOI]

Prentice-Hall, ISBN: 0-13-273426-5, 1981

1980

On the Performance of Balanced Hashing Functions When the Keys Are Not Equiprobable.

[BibT_eX]

[DOI]

Philip A. Bernstein

ACM Trans. Program. Lang. Syst., 1980

The Complexity of Coloring Circular Arcs and Chords.

[BibT_eX]

[DOI]

M. R. Garey

Gerald L. Miller

SIAM J. Algebraic Discret. Methods, 1980

Flowshop scheduling with limited temporary storage.

[BibT_eX]

[DOI]

J. ACM, 1980

Local Search for the Asymmetric Traveling Salesman Problem.

[BibT_eX]

[DOI]

Oper. Res., 1980

A Worst-Case Analysis of Nearest Neighbor Searching by Projection.

[BibT_eX]

[DOI]

Jon Louis Bentley

Proceedings of the Automata, 1980

Symmetric Space-Bounded Computation (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1980

Algebraic Dependencies (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979

Scheduling Interval-Ordered Tasks.

[BibT_eX]

[DOI]

SIAM J. Comput., 1979

The serializability of concurrent database updates.

[BibT_eX]

[DOI]

J. ACM, 1979

Optimality of the Fast Fourier transform.

[BibT_eX]

[DOI]

J. ACM, 1979

Efficient Search for Rationals.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1979

Bounds for sorting by prefix reversal.

[BibT_eX]

[DOI]

William H. Gates

Discret. Math., 1979

The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1979

Locking Policies: Safety and Freedom from Deadlock

[BibT_eX]

[DOI]

H. T. Kung

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).

[BibT_eX]

[DOI]

Philip A. Bernstein

James B. Rothnie Jr.

Nathan Goodman

IEEE Trans. Software Eng., 1978

The complexity of the capacitated tree problem.

[BibT_eX]

[DOI]

Networks, 1978

The adjacency relation on the traveling salesman polytope is NP-Complete.

[BibT_eX]

[DOI]

Math. Program., 1978

Some Examples of Difficult Traveling Salesman Problems.

[BibT_eX]

[DOI]

Oper. Res., 1978

1977

The Euclidean Traveling Salesman Problem is NP-Complete.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1977

On the Complexity of Local Search for the Traveling Salesman Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1977

1976

On the complexity of edge traversing.

[BibT_eX]

[DOI]

J. ACM, 1976

The NP-Completeness of the bandwidth minimization problem.

[BibT_eX]

[DOI]

Computing, 1976

Some Complexity Results for the Traveling Salesman Problem

[BibT_eX]

[DOI]