Mihalis Yannakakis

Yuhao Li

Electron. Colloquium Comput. Complex., 2024

Computing a Fixed Point of Contraction Maps in Polynomial Queries.

[BibT_eX]

[DOI]

Yuhao Li

CoRR, 2024

Smoothed Complexity of SWAP in Local Graph Partitioning.

[BibT_eX]

[DOI]

Emmanouil V. Vlatakis-Gkaragkounis

Chenghao Guo

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Reducing Tarski to Unique Tarski (in the Black-box Model).

[BibT_eX]

[DOI]

Yuhao Li

Electron. Colloquium Comput. Complex., 2023

The Smoothed Complexity of Policy Iteration for Markov Decision Processes.

[BibT_eX]

[DOI]

Miranda Christ

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP.

[BibT_eX]

[DOI]

Amol Pasarkar

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Technical Perspective: Structure and Complexity of Bag Consistency.

[BibT_eX]

[DOI]

SIGMOD Rec., 2022

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

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

[BibT_eX]

[DOI]

Christos Harilaos Papadimitriou

CoRR, 2022

Computational Hardness of the Hylland-Zeckhauser Scheme.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

The Platform Design Problem.

[BibT_eX]

[DOI]

Kiran Vodrahalli

Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Epinoia: Intent Checker for Stateful Networks.

[BibT_eX]

[DOI]

Proceedings of the 30th International Conference on Computer Communications and Networks, 2021

2020

Doubly Balanced Connected Graph Partitioning.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations.

[BibT_eX]

[DOI]

Math. Oper. Res., 2020

Planar graphs that need four pages.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2020

Smoothed complexity of local max-cut and binary max-CSP.

[BibT_eX]

[DOI]

Emmanouil V. Vlatakis-Gkaragkounis

Chenghao Guo

Xinzhi Zhang

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

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

[BibT_eX]

[DOI]

Aviad Rubinstein

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

Homa: An Efficient Topology and Route Management Approach in SD-WAN Overlays.

[BibT_eX]

[DOI]

Proceedings of the 39th IEEE Conference on Computer Communications, 2020

2019

REACT to Cyber Attacks on Power Grids.

[BibT_eX]

[DOI]

IEEE Trans. Netw. Sci. Eng., 2019

Recursive stochastic games with positive rewards.

[BibT_eX]

[DOI]

Dominik Wojtczak

Theor. Comput. Sci., 2019

The Complexity of Finding <i>S</i>-factors in Regular Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Alembic: Automated Model Inference for Stateful Network Functions.

[BibT_eX]

[DOI]

Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation, 2019

Fixed Point Computation Problems and Facets of Complexity (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Reachability for Branching Concurrent Stochastic Games.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

The Complexity of Finding S-Factors in Regular Graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018

Power Grid State Estimation Following a Joint Cyber and Physical Attack.

[BibT_eX]

[DOI]

IEEE Trans. Control. Netw. Syst., 2018

REACT to Cyber-Physical Attacks on Power grids (Extended Abstract).

[BibT_eX]

[DOI]

SIGMETRICS Perform. Evaluation Rev., 2018

Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes.

[BibT_eX]

[DOI]

Inf. Comput., 2018

The complexity of optimal multidimensional pricing for a unit-demand buyer.

[BibT_eX]

[DOI]

Games Econ. Behav., 2018

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.

[BibT_eX]

[DOI]

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

2017

A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

The Complexity of Non-Monotone Markets.

[BibT_eX]

[DOI]

Dimitris Paparas

J. ACM, 2017

On the Complexity of Bundle-Pricing and Simple Mechanisms.

[BibT_eX]

[DOI]

CoRR, 2017

2016

How Good is the Chord Algorithm?

[BibT_eX]

[DOI]

Constantinos Daskalakis

SIAM J. Comput., 2016

2015

Upper Bounds for Newton's Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata.

[BibT_eX]

[DOI]

J. ACM, 2015

Recursive Markov Decision Processes and Recursive Stochastic Games.

[BibT_eX]

[DOI]

J. ACM, 2015

Joint Cyber and Physical Attacks on Power Grids: Graph Theoretical Approaches for Information Recovery.

[BibT_eX]

[DOI]

Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2015

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

The Complexity of Optimal Multidimensional Pricing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Analysis of Boolean Programs.

[BibT_eX]

[DOI]

Patrice Godefroid

Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2013

Stochastic Context-Free Grammars, Regular Languages, and Newton's Method.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Model Checking of Recursive Probabilistic Systems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2012

Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars

[BibT_eX]

[DOI]

CoRR, 2012

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Computation of Least Fixed Points.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

Market equilibrium under separable, piecewise-linear, concave utilities.

[BibT_eX]

[DOI]

J. ACM, 2011

Temporal Synthesis for Bounded Systems and Environments.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

2010

On the Complexity of Nash Equilibria and Other Fixed Points.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

An impossibility theorem for price-adjustment mechanisms.

[BibT_eX]

[DOI]

Proc. Natl. Acad. Sci. USA, 2010

Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems.

[BibT_eX]

[DOI]

Dominik Wojtczak

Perform. Evaluation, 2010

Computation of Equilibria and Stable Solutions.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

2009

Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations.

[BibT_eX]

[DOI]

J. ACM, 2009

Equilibria, fixed points, and complexity classes.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2009

Computational Aspects of Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

2008

Recursive Concurrent Stochastic Games.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2008

Multi-Objective Model Checking of Markov Decision Processes.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2008

Automata, Probability, and Recursion.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Applications of Automata, 2008

Succinct approximate convex pareto curves.

[BibT_eX]

[DOI]

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

2007

On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract).

[BibT_eX]

[DOI]

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

Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

2006

Adaptive Model Checking.

[BibT_eX]

[DOI]

Alex Groce

Log. J. IGPL, 2006

Succinct Approximation of Trade-Off Curves.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

A note on broadcast encryption key management with applications to large scale emergency alert systems.

[BibT_eX]

[DOI]

Guoqiang Shu

Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), 2006

Recursion and Probability.

[BibT_eX]

[DOI]

Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

Analysis of Recursive Probabilistic Models.

[BibT_eX]

[DOI]

Proceedings of the Automated Technology for Verification and Analysis, 2006

2005

Analysis of recursive state machines.

[BibT_eX]

[DOI]

ACM Trans. Program. Lang. Syst., 2005

Efficiently computing succinct trade-off curves.

[BibT_eX]

[DOI]

Sergei Vassilvitskii

Theor. Comput. Sci., 2005

Realizability and verification of MSC graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Algorithmic Verification of Recursive Probabilistic State Machines.

[BibT_eX]

[DOI]

Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2005

Testing hierarchical systems.

[BibT_eX]

[DOI]

Damon Mosk-Aoyama

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

Checking LTL Properties of Recursive Markov Chains.

[BibT_eX]

[DOI]

Proceedings of the Second International Conference on the Quantitative Evaluaiton of Systems (QEST 2005), 2005

Probability and Recursion.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004

Guest Editors' foreword.

[BibT_eX]

[DOI]

Sampath Kannan

J. Comput. Syst. Sci., 2004

Multiway cuts in node weighted graphs.

[BibT_eX]

[DOI]

J. Algorithms, 2004

Protocol System Integration, Interface and Interoperability.

[BibT_eX]

[DOI]

Christine Liu

Proceedings of the Principles of Distributed Systems, 8th International Conference, 2004

Testing, Optimizaton, and Games.

[BibT_eX]

[DOI]

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

2003

Inference of Message Sequence Charts.

[BibT_eX]

[DOI]

IEEE Trans. Software Eng., 2003

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

Compression of Partially Ordered Strings.

[BibT_eX]

[DOI]

Proceedings of the CONCUR 2003, 2003

2002

Closed Partition Lattice and Machine Decomposition.

[BibT_eX]

[DOI]

IEEE Trans. Computers, 2002

Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.

[BibT_eX]

[DOI]

SIAM Rev., 2002

Black Box Checking.

[BibT_eX]

[DOI]

Moshe Y. Vardi

J. Autom. Lang. Comb., 2002

Testing and Checking of Finite State Systems.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

AMC: An Adaptive Model Checker.

[BibT_eX]

[DOI]

Alex Groce

Proceedings of the Computer Aided Verification, 14th International Conference, 2002

2001

Model checking of hierarchical state machines.

[BibT_eX]

[DOI]

ACM Trans. Program. Lang. Syst., 2001

Approximation of Multiobjective Optimization Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Multiobjective Query Optimization.

[BibT_eX]

[DOI]

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

Analysis of Recursive State Machines.

[BibT_eX]

[DOI]

Proceedings of the Computer Aided Verification, 13th International Conference, 2001

2000

Reminiscences on Influential Papers.

[BibT_eX]

SIGMOD Rec., 2000

Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2000

Hierarchical State Machines.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 2000

From Rule-based to Automata-based Testing.

[BibT_eX]

Proceedings of the Formal Techniques for Distributed System Development, 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

1999

On the Complexity of Database Queries.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

A Convex Relaxation for the Asymmetric TSP.

[BibT_eX]

[DOI]

Santosh S. Vempala

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Communicating Hierarchical State Machines.

[BibT_eX]

[DOI]

Sampath Kannan

Proceedings of the Automata, 1999

Model Checking of Message Sequence Charts.

[BibT_eX]

[DOI]

Proceedings of the CONCUR '99: Concurrency Theory, 1999

1998

Markov decision processes and regular events.

[BibT_eX]

[DOI]

IEEE Trans. Autom. Control., 1998

On the Complexity of Protein Folding.

[BibT_eX]

[DOI]

Pierluigi Crescenzi

Deborah Goldman

Antonio Piccolboni

J. Comput. Biol., 1998

On the Complexity of Protein Folding (Extended Abstract).

[BibT_eX]

[DOI]

Pierluigi Crescenzi

Deborah Goldman

Antonio Piccolboni

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

On the complexity of protein folding (abstract).

[BibT_eX]

[DOI]

Pierluigi Crescenzi

Deborah Goldman

Antonio Piccolboni

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

Protocol Feature Interactions.

[BibT_eX]

Proceedings of the Formal Description Techniques and Protocol Specification, 1998

Testing for Finite State Systems.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 12th International Workshop, 1998

1997

Tie-Breaking Semantics and Structural Totality.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1997

An Efficient Algorithm for Minimizing Real-Time Transition Systems.

[BibT_eX]

[DOI]

Formal Methods Syst. Des., 1997

Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees.

[BibT_eX]

[DOI]

Algorithmica, 1997

Existence of Reduction Hierarchies.

[BibT_eX]

[DOI]

Orna Kupferman

Robert P. Kurshan

Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996

Perspectives on database theory.

[BibT_eX]

[DOI]

SIGACT News, 1996

Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

Principles and methods of testing finite state machines-a survey.

[BibT_eX]

[DOI]

Proc. IEEE, 1996

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

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

Optimization problems from feature testing of communication protocols.

[BibT_eX]

[DOI]

Proceedings of the 1996 International Conference on Network Protocols, 1996

Searching a Fixed Graph.

[BibT_eX]

[DOI]

Elias Koutsoupias

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

On nested depth first search.

[BibT_eX]

[DOI]

Gerard J. Holzmann

Proceedings of the Spin Verification System, 1996

1995

Timing Verification by Successive Approximation

[BibT_eX]

[DOI]

Inf. Comput., April, 1995

Testing Finite State Machines: Fault Detection.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

On Datalog vs. Polynomial Time.

[BibT_eX]

[DOI]

Foto N. Afrati

Stavros S. Cosmadakis

J. Comput. Syst. Sci., 1995

The Complexity of Probabilistic Verification.

[BibT_eX]

[DOI]

J. ACM, 1995

Distinguishing tests for nondeterministic and probabilistic machines.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

1994

Testing Finite-State Machines: State Identification and Verification.

[BibT_eX]

[DOI]

IEEE Trans. Computers, 1994

The Complexity of Multiterminal Cuts.

[BibT_eX]

[DOI]

Elias Dahlhaus

Paul D. Seymour

SIAM J. Comput., 1994

On the Approximation of Maximum Satisfiability.

[BibT_eX]

[DOI]

J. Algorithms, 1994

On the Hardness of Approximating Minimization Problems.

[BibT_eX]

[DOI]

Carsten Lund

J. ACM, 1994

Linear Approximation of Shortest Superstrings.

[BibT_eX]

[DOI]

J. ACM, 1994

On complexity as bounded rationality (extended abstract).

[BibT_eX]

[DOI]

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

Multiway Cuts in Directed and Node Weighted Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Some Open Problems in Approximation.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, Second Italian Conference, 1994

1993

The Traveling Salesman Problem with Distances One and Two.

[BibT_eX]

[DOI]

Math. Oper. Res., 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

Recent Developments on the Approximability of Combinatorial Problems.

[BibT_eX]

[DOI]

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

The Approximation of Maximum Subgraph Problems.

[BibT_eX]

[DOI]

Carsten Lund

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 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

Minimum and Maximum Delay Problems in Real-Time Systems.

[BibT_eX]

[DOI]

Formal Methods Syst. Des., 1992

Memory-Efficient Algorithms for the Verification of Temporal Properties.

[BibT_eX]

[DOI]

Formal Methods Syst. Des., 1992

Online Minimization of Transition Systems (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 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

Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991

Shortest Paths Without a Map.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

High-Probability Parallel Transitive-Closure Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 1991

Simple Local Search Problems That are Hard to Solve.

[BibT_eX]

[DOI]

Alejandro A. Schäffer

SIAM J. Comput., 1991

Expressing Combinatorial Optimization Problems by Linear Programs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

Optimization, Approximation, and Complexity Classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

Modularity of Cycles and Paths in Graphs.

[BibT_eX]

[DOI]

Esther M. Arkin

J. ACM, 1991

The Input/Output Complexity of Transitive Closure.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 1991

Testing Finite State Machines (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 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

1990

Towards an Architecture-Independent Analysis of Parallel Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

On recognizing integer polyhedra.

[BibT_eX]

[DOI]

Comb., 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

The Analysis of Local Search Problems and Their Heuristics.

[BibT_eX]

[DOI]

Proceedings of the STACS 90, 1990

Graph-Theoretic Methods in Database Theory.

[BibT_eX]

[DOI]

Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1990

Markov Decision Processes and Regular Events (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989

Embedding Planar Graphs in Four Pages.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1989

Deleting Completed Transactions.

[BibT_eX]

[DOI]

Thanasis Hadzilacos

J. Comput. Syst. Sci., 1989

Optimal Scheduling of Products with Two Subassemblies on a Single Machine.

[BibT_eX]

[DOI]

Ardavan Nozari

Oper. Res., 1989

Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1989

1988

How Easy is Local Search?

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1988

On Generating All Maximal Independent Sets.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 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

Verifying Temporal Properties of Finite-State Probabilistic Programs

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

The Complexity of Reliable Concurrency Control.

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

The Maximum k-Colorable Subgraph Problem for Chordal Graphs.

[BibT_eX]

[DOI]

Fanica Gavril

Inf. Process. Lett., 1987

1986

A Note on Succinct Representations of Graphs

[BibT_eX]

[DOI]

Inf. Control., December, 1986

Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.

[BibT_eX]

[DOI]

Ouri Wolfson

J. Comput. Syst. Sci., 1986

Querying Weak Instances.

[BibT_eX]

Adv. Comput. Res., 1986

Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Linear and Book Embeddings of Graphs.

[BibT_eX]

[DOI]

Proceedings of the VLSI Algorithms and Architectures, 1986

1985

A Polynomial Algorithm for the Min-Cut Linear Arrangement of Trees

[BibT_eX]

[DOI]

J. ACM, October, 1985

Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.

[BibT_eX]

[DOI]

Robert Endre Tarjan

SIAM J. Comput., 1985

On a Class of Totally Unimodular Matrices.

[BibT_eX]

[DOI]

Math. Oper. Res., 1985

How Easy Is Local Search? (Extended Abstract)

[BibT_eX]

[DOI]

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

1984

Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.

[BibT_eX]

[DOI]

Robert Endre Tarjan

SIAM J. Comput., 1984

Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum.

[BibT_eX]

[DOI]

Math. Oper. Res., 1984

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

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1984

Independent Database Schemas.

[BibT_eX]

[DOI]

Marc H. Graham

J. Comput. Syst. Sci., 1984

Serializability by Locking.

[BibT_eX]

[DOI]

J. ACM, 1984

On Monotone Formulae with Restricted Depth (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

On the Desirability of Acyclic Database Schemes

[BibT_eX]

[DOI]

J. ACM, July, 1983

Tools for Template Dependencies.

[BibT_eX]

[DOI]

SIAM J. Comput., 1983

On Notions of Information Transfer in VLSI Circuits

[BibT_eX]

[DOI]

Alfred V. Aho

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

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

[BibT_eX]

[DOI]

Paris C. Kanellakis

Stavros S. Cosmadakis

Proceedings of the Automata, 1983

A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract)

[BibT_eX]

[DOI]

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

1982

Freedom from Deadlock of Safe Locking Policies.

[BibT_eX]

[DOI]

SIAM J. Comput., 1982

Algebraic Dependencies.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1982

A Theory of Safe Locking Policies in Database Systems.

[BibT_eX]

[DOI]

J. ACM, 1982

The complexity of restricted spanning tree problems.

[BibT_eX]

[DOI]

J. ACM, 1982

1981

Node-Deletion Problems on Bipartite Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1981

Edge-Deletion Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1981

On the Complexity of Testing Implications of Functional and Join Dependencies.

[BibT_eX]

[DOI]

David Maier

Yehoshua Sagiv

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

Richard M. Karp

Oliver Vornberger

Inf. Process. Lett., 1981

Algorithms for Acyclic Database Schemes

[BibT_eX]

Proceedings of the Very Large Data Bases, 1981

Issues of Correctness in Database Concurrency Control by Locking

[BibT_eX]

[DOI]

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Properties of Acyclic Database Schemes

[BibT_eX]

[DOI]

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 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

1980

The Node-Deletion Problem for Hereditary Properties is NP-Complete.

[BibT_eX]

[DOI]

John M. Lewis

J. Comput. Syst. Sci., 1980

Equivalences Among Relational Expressions with the Union and Difference Operators.

[BibT_eX]

[DOI]

Yehoshua Sagiv

J. ACM, 1980

Testing the Universal Instance Assumption.

[BibT_eX]

[DOI]

Peter Honeyman

Richard E. Ladner

Inf. Process. Lett., 1980

Algebraic Dependencies (Extended Abstract)

[BibT_eX]

[DOI]

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

1979

Topological Characterization of Families of Graphs Generated by Certain Types of Graph Grammars

[BibT_eX]

[DOI]

Theodosios Pavlidis

Inf. Control., July, 1979

Scheduling Interval-Ordered Tasks.

[BibT_eX]

[DOI]

SIAM J. Comput., 1979

The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems.

[BibT_eX]

[DOI]

J. ACM, 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

Modeling Communications Protocols by Automata

[BibT_eX]

[DOI]

Alfred V. Aho

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

Equivalence among Relational Expressions with the Union and Difference Operation.

[BibT_eX]

Yehoshua Sagiv

Proceedings of the Fourth International Conference on Very Large Data Bases, 1978

Node- and Edge-Deletion NP-Complete Problems

[BibT_eX]

[DOI]