# Mihalis Yannakakis

According to our database1, Mihalis Yannakakis authored at least 206 papers between 1978 and 2021.

Collaborative distances:

## ACM Fellow

ACM Fellow 1998, "For seminal contributions to the foundations of computer science, the principles of database systems, and the links between complexity theory and combinatorial optimization.".

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2021
Computational Hardness of the Hylland-Zeckhauser Scheme.
CoRR, 2021

Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020
Doubly Balanced Connected Graph Partitioning.
ACM Trans. Algorithms, 2020

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations.
Math. Oper. Res., 2020

Planar graphs that need four pages.
J. Comb. Theory, Ser. B, 2020

The Platform Design Problem.
CoRR, 2020

Smoothed complexity of local max-cut and binary max-CSP.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

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

Homa: An Efficient Topology and Route Management Approach in SD-WAN Overlays.
Proceedings of the 39th IEEE Conference on Computer Communications, 2020

2019
REACT to Cyber Attacks on Power Grids.
IEEE Trans. Netw. Sci. Eng., 2019

Recursive stochastic games with positive rewards.
Theor. Comput. Sci., 2019

The Complexity of Finding {\$S\$}-factors in Regular Graphs.
Electron. Colloquium Comput. Complex., 2019

Alembic: Automated Model Inference for Stateful Network Functions.
Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation, 2019

Fixed Point Computation Problems and Facets of Complexity (Invited Talk).
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Reachability for Branching Concurrent Stochastic Games.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Power Grid State Estimation Following a Joint Cyber and Physical Attack.
IEEE Trans. Control. Netw. Syst., 2018

REACT to Cyber-Physical Attacks on Power grids (Extended Abstract).
SIGMETRICS Perform. Evaluation Rev., 2018

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

The complexity of optimal multidimensional pricing for a unit-demand buyer.
Games Econ. Behav., 2018

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

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

2017
A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes.
SIAM J. Comput., 2017

The Complexity of Non-Monotone Markets.
J. ACM, 2017

On the Complexity of Bundle-Pricing and Simple Mechanisms.
CoRR, 2017

2016
How Good is the Chord Algorithm?
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.
J. ACM, 2015

Recursive Markov Decision Processes and Recursive Stochastic Games.
J. ACM, 2015

Joint Cyber and Physical Attacks on Power Grids: Graph Theoretical Approaches for Information Recovery.
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.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
The Complexity of Optimal Multidimensional Pricing.
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.
Electron. Colloquium Comput. Complex., 2013

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

Stochastic Context-Free Grammars, Regular Languages, and Newton's Method.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
Model Checking of Recursive Probabilistic Systems.
ACM Trans. Comput. Log., 2012

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

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Computation of Least Fixed Points.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011
Market equilibrium under separable, piecewise-linear, concave utilities.
J. ACM, 2011

Temporal Synthesis for Bounded Systems and Environments.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

2010
On the Complexity of Nash Equilibria and Other Fixed Points.
SIAM J. Comput., 2010

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

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

Computation of Equilibria and Stable Solutions.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

2009
Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems.
SIAM J. Comput., 2009

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

Equilibria, fixed points, and complexity classes.
Comput. Sci. Rev., 2009

Computational Aspects of Equilibria.
Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

2008
Recursive Concurrent Stochastic Games.
Log. Methods Comput. Sci., 2008

Multi-Objective Model Checking of Markov Decision Processes.
Log. Methods Comput. Sci., 2008

Automata, Probability, and Recursion.
Proceedings of the Implementation and Applications of Automata, 2008

Succinct approximate convex pareto curves.
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).
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.
Proceedings of the Approximation, 2007

2006
Adaptive Model Checking.
Log. J. IGPL, 2006

Succinct Approximation of Trade-Off Curves.
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.
Proceedings of the STACS 2006, 2006

A note on broadcast encryption key management with applications to large scale emergency alert systems.
Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), 2006

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

Analysis of Recursive Probabilistic Models.
Proceedings of the Automated Technology for Verification and Analysis, 2006

2005
Analysis of recursive state machines.
ACM Trans. Program. Lang. Syst., 2005

Efficiently computing succinct trade-off curves.
Theor. Comput. Sci., 2005

Realizability and verification of MSC graphs.
Theor. Comput. Sci., 2005

Algorithmic Verification of Recursive Probabilistic State Machines.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2005

Testing hierarchical systems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Checking LTL Properties of Recursive Markov Chains.
Proceedings of the Second International Conference on the Quantitative Evaluaiton of Systems (QEST 2005), 2005

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

2004
Guest Editors' foreword.
J. Comput. Syst. Sci., 2004

Multiway cuts in node weighted graphs.
J. Algorithms, 2004

Protocol System Integration, Interface and Interoperability.
Proceedings of the Principles of Distributed Systems, 8th International Conference, 2004

Testing, Optimizaton, and Games.
Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

2003
Inference of Message Sequence Charts.
IEEE Trans. Software Eng., 2003

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems.
J. Comput. Syst. Sci., 2003

Compression of Partially Ordered Strings.
Proceedings of the CONCUR 2003, 2003

2002
Closed Partition Lattice and Machine Decomposition.
IEEE Trans. Computers, 2002

Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.
SIAM Rev., 2002

Black Box Checking.
J. Autom. Lang. Comb., 2002

Testing and Checking of Finite State Systems.
Proceedings of the LATIN 2002: Theoretical Informatics, 2002

AMC: An Adaptive Model Checker.
Proceedings of the Computer Aided Verification, 14th International Conference, 2002

2001
Model checking of hierarchical state machines.
ACM Trans. Program. Lang. Syst., 2001

Approximation of Multiobjective Optimization Problems.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

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

Analysis of Recursive State Machines.
Proceedings of the Computer Aided Verification, 13th International Conference, 2001

2000
Reminiscences on Influential Papers.
SIGMOD Rec., 2000

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

Hierarchical State Machines.
Proceedings of the Theoretical Computer Science, 2000

From Rule-based to Automata-based Testing.
Proceedings of the Formal Techniques for Distributed System Development, 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

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

A Convex Relaxation for the Asymmetric TSP.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Communicating Hierarchical State Machines.
Proceedings of the Automata, 1999

Model Checking of Message Sequence Charts.
Proceedings of the CONCUR '99: Concurrency Theory, 1999

1998
Markov decision processes and regular events.
IEEE Trans. Autom. Control., 1998

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

On the Complexity of Protein Folding (Extended Abstract).
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

Protocol Feature Interactions.
Proceedings of the Formal Description Techniques and Protocol Specification, 1998

Testing for Finite State Systems.
Proceedings of the Computer Science Logic, 12th International Workshop, 1998

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

An Efficient Algorithm for Minimizing Real-Time Transition Systems.
Formal Methods Syst. Des., 1997

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

Existence of Reduction Hierarchies.
Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996
Perspectives on database theory.
SIGACT News, 1996

Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.
SIAM J. Comput., 1996

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

Optimization problems from feature testing of communication protocols.
Proceedings of the 1996 International Conference on Network Protocols, 1996

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

On nested depth first search.
Proceedings of the Spin Verification System, 1996

1995
Timing Verification by Successive Approximation
Inf. Comput., April, 1995

Testing Finite State Machines: Fault Detection.
J. Comput. Syst. Sci., 1995

On Datalog vs. Polynomial Time.
J. Comput. Syst. Sci., 1995

The Complexity of Probabilistic Verification.
J. ACM, 1995

Distinguishing tests for nondeterministic and probabilistic machines.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

1994
Testing Finite-State Machines: State Identification and Verification.
IEEE Trans. Computers, 1994

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

On the Approximation of Maximum Satisfiability.
J. Algorithms, 1994

On the Hardness of Approximating Minimization Problems.
J. ACM, 1994

Linear Approximation of Shortest Superstrings.
J. ACM, 1994

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

Multiway Cuts in Directed and Node Weighted Graphs.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Some Open Problems in Approximation.
Proceedings of the Algorithms and Complexity, Second Italian Conference, 1994

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

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

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

Recent Developments on the Approximability of Combinatorial Problems.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

The Approximation of Maximum Subgraph Problems.
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.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

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

1992
Minimum and Maximum Delay Problems in Real-Time Systems.
Formal Methods Syst. Des., 1992

Memory-Efficient Algorithms for the Verification of Temporal Properties.
Formal Methods Syst. Des., 1992

Online Minimization of Transition Systems (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

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

Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

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

High-Probability Parallel Transitive-Closure Algorithms.
SIAM J. Comput., 1991

Simple Local Search Problems That are Hard to Solve.
SIAM J. Comput., 1991

Expressing Combinatorial Optimization Problems by Linear Programs.
J. Comput. Syst. Sci., 1991

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

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

The Input/Output Complexity of Transitive Closure.
Ann. Math. Artif. Intell., 1991

Testing Finite State Machines (Extended Abstract)
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
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 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

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

On recognizing integer polyhedra.
Comb., 1990

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

The Analysis of Local Search Problems and Their Heuristics.
Proceedings of the STACS 90, 1990

Graph-Theoretic Methods in Database Theory.
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1990

Markov Decision Processes and Regular Events (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989
Embedding Planar Graphs in Four Pages.
J. Comput. Syst. Sci., 1989

Deleting Completed Transactions.
J. Comput. Syst. Sci., 1989

Optimal Scheduling of Products with Two Subassemblies on a Single Machine.
Oper. Res., 1989

Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs.
Discret. Appl. Math., 1989

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

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

Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 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

Verifying Temporal Properties of Finite-State Probabilistic Programs
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

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

The Maximum k-Colorable Subgraph Problem for Chordal Graphs.
Inf. Process. Lett., 1987

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

Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.
J. Comput. Syst. Sci., 1986

Querying Weak Instances.
Adv. Comput. Res., 1986

Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Linear and Book Embeddings of Graphs.
Proceedings of the VLSI Algorithms and Architectures, 1986

1985
A Polynomial Algorithm for the Min-Cut Linear Arrangement of Trees
J. ACM, October, 1985

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

On a Class of Totally Unimodular Matrices.
Math. Oper. Res., 1985

How Easy Is Local Search? (Extended Abstract)
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.
SIAM J. Comput., 1984

Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum.
Math. Oper. Res., 1984

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

Independent Database Schemas.
J. Comput. Syst. Sci., 1984

Serializability by Locking.
J. ACM, 1984

On Monotone Formulae with Restricted Depth (Preliminary Version)
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983
On the Desirability of Acyclic Database Schemes
J. ACM, July, 1983

Tools for Template Dependencies.
SIAM J. Comput., 1983

On Notions of Information Transfer in VLSI Circuits
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

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

A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982
Freedom from Deadlock of Safe Locking Policies.
SIAM J. Comput., 1982

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

A Theory of Safe Locking Policies in Database Systems.
J. ACM, 1982

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

1981
Node-Deletion Problems on Bipartite Graphs.
SIAM J. Comput., 1981

Edge-Deletion Problems.
SIAM J. Comput., 1981

On the Complexity of Testing Implications of Functional and Join Dependencies.
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

Algorithms for Acyclic Database Schemes
Proceedings of the Very Large Data Bases, 1981

Issues of Correctness in Database Concurrency Control by Locking
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Properties of Acyclic Database Schemes
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)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
The Node-Deletion Problem for Hereditary Properties is NP-Complete.
J. Comput. Syst. Sci., 1980

Equivalences Among Relational Expressions with the Union and Difference Operators.
J. ACM, 1980

Testing the Universal Instance Assumption.
Inf. Process. Lett., 1980

Algebraic Dependencies (Extended Abstract)
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
Inf. Control., July, 1979

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

The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems.
J. ACM, 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

Modeling Communications Protocols by Automata
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
Equivalence among Relational Expressions with the Union and Difference Operation.
Proceedings of the Fourth International Conference on Very Large Data Bases, 1978

Node- and Edge-Deletion NP-Complete Problems
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978