| 2024 | SODA | Smoothed Complexity of SWAP in Local Graph Partitioning. | Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis |
| 2024 | STOC | Computing a Fixed Point of Contraction Maps in Polynomial Queries. | Xi Chen, Yuhao Li, Mihalis Yannakakis |
| 2023 | STOC | The Smoothed Complexity of Policy Iteration for Markov Decision Processes. | Miranda Christ, Mihalis Yannakakis |
| 2022 | SODA | Computational Hardness of the Hylland-Zeckhauser Scheme. | Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis |
| 2021 | ICCCN | Epinoia: Intent Checker for Stateful Networks. | Huazhe Wang, Puneet Sharma, Faraz Ahmed, Joon-Myung Kang, Chen Qian, Mihalis Yannakakis |
| 2020 | INFOCOM | Homa: An Efficient Topology and Route Management Approach in SD-WAN Overlays. | Diman Zad Tootaghaj, Faraz Ahmed, Puneet Sharma, Mihalis Yannakakis |
| 2020 | STOC | Smoothed complexity of local max-cut and binary max-CSP. | Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang |
| 2019 | ICALP | Reachability for Branching Concurrent Stochastic Games. | Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis |
| 2019 | ICALP | Fixed Point Computation Problems and Facets of Complexity (Invited Talk). | Mihalis Yannakakis |
| 2019 | NSDI | Alembic: Automated Model Inference for Stateful Network Functions. | Soo-Jin Moon, Jeffrey Helt, Yifei Yuan, Yves Bieri, Sujata Banerjee, Vyas Sekar, Wenfei Wu, Mihalis Yannakakis, Ying Zhang |
| 2018 | SODA | On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer. | Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis |
| 2017 | SODA | Doubly Balanced Connected Graph Partitioning. | Saleh Soltan, Mihalis Yannakakis, Gil Zussman |
| 2015 | FOCS | On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. | Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis |
| 2015 | ICALP | Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes. | Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
| 2015 | SIGMETRICS | Joint Cyber and Physical Attacks on Power Grids: Graph Theoretical Approaches for Information Recovery. | Saleh Soltan, Mihalis Yannakakis, Gil Zussman |
| 2014 | SODA | The Complexity of Optimal Multidimensional Pricing. | Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis |
| 2013 | CAV | Upper Bounds for Newton's Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata. | Alistair Stewart, Kousha Etessami, Mihalis Yannakakis |
| 2013 | ICALP | Stochastic Context-Free Grammars, Regular Languages, and Newton's Method. | Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
| 2013 | STOC | The complexity of non-monotone markets. | Xi Chen, Dimitris Paparas, Mihalis Yannakakis |
| 2013 | TACAS | Analysis of Boolean Programs. | Patrice Godefroid, Mihalis Yannakakis |
| 2012 | ICALP | Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations. | Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
| 2012 | MFCS | Computation of Least Fixed Points. | Mihalis Yannakakis |
| 2012 | STOC | Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars. | Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
| 2011 | STACS | Temporal Synthesis for Bounded Systems and Environments. | Orna Kupferman, Yoad Lustig, Moshe Y. Vardi, Mihalis Yannakakis |
| 2010 | SODA | How Good is the Chord Algorithm?. | Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis |
| 2010 | SSS | Computation of Equilibria and Stable Solutions. | Mihalis Yannakakis |
| 2009 | SAGT | Computational Aspects of Equilibria. | Mihalis Yannakakis |
| 2008 | ICALP | Recursive Stochastic Games with Positive Rewards. | Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis |
| 2008 | SODA | Succinct approximate convex pareto curves. | Ilias Diakonikolas, Mihalis Yannakakis |
| 2008 | STACS | Equilibria, Fixed Points, and Complexity Classes. | Mihalis Yannakakis |
| 2007 | FOCS | On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). | Kousha Etessami, Mihalis Yannakakis |
| 2007 | TACAS | Multi-objective Model Checking of Markov Decision Processes. | Kousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis |
| 2006 | ATVA | Analysis of Recursive Probabilistic Models. | Mihalis Yannakakis |
| 2006 | ICALP | Recursive Concurrent Stochastic Games. | Kousha Etessami, Mihalis Yannakakis |
| 2006 | STACS | Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games. | Kousha Etessami, Mihalis Yannakakis |
| 2005 | ICALP | Recursive Markov Decision Processes and Recursive Stochastic Games. | Kousha Etessami, Mihalis Yannakakis |
| 2005 | ISAAC | Probability and Recursion. | Kousha Etessami, Mihalis Yannakakis |
| 2005 | SODA | Testing hierarchical systems. | Damon Mosk-Aoyama, Mihalis Yannakakis |
| 2005 | STACS | Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. | Kousha Etessami, Mihalis Yannakakis |
| 2005 | TACAS | Algorithmic Verification of Recursive Probabilistic State Machines. | Kousha Etessami, Mihalis Yannakakis |
| 2004 | ICALP | Efficiently Computing Succinct Trade-Off Curves. | Sergei Vassilvitskii, Mihalis Yannakakis |
| 2004 | ICALP | Testing, Optimizaton, and Games. | Mihalis Yannakakis |
| 2004 | LICS | Testing, Optimizaton, and Games. | Mihalis Yannakakis |
| 2004 | OPODIS | Protocol System Integration, Interface and Interoperability. | David Lee, Christine Liu, Mihalis Yannakakis |
| 2003 | CONCUR | Compression of Partially Ordered Strings. | Rajeev Alur, Swarat Chaudhuri, Kousha Etessami, Sudipto Guha, Mihalis Yannakakis |
| 2002 | CAV | AMC: An Adaptive Model Checker. | Alex Groce, Doron A. Peled, Mihalis Yannakakis |
| 2002 | LATIN | Testing and Checking of Finite State Systems. | Mihalis Yannakakis |
| 2002 | TACAS | Adaptive Model Checking. | Alex Groce, Doron A. Peled, Mihalis Yannakakis |
| 2001 | CAV | Analysis of Recursive State Machines. | Rajeev Alur, Kousha Etessami, Mihalis Yannakakis |
| 2001 | ICALP | Realizability and Verification of MSC Graphs. | Rajeev Alur, Kousha Etessami, Mihalis Yannakakis |
| 2001 | PODS | Multiobjective Query Optimization. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 2001 | WADS | Approximation of Multiobjective Optimization Problems. | Mihalis Yannakakis |
| 2000 | FOCS | On the Approximability of Trade-offs and Optimal Access of Web Sources. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 2000 | FORTE | From Rule-based to Automata-based Testing. | Kousha Etessami, Mihalis Yannakakis |
| 2000 | ICSE | Inference of message sequence charts. | Rajeev Alur, Kousha Etessami, Mihalis Yannakakis |
| 1999 | CONCUR | Model Checking of Message Sequence Charts. | Rajeev Alur, Mihalis Yannakakis |
| 1999 | FORTE | Black Box Checking. | Doron A. Peled, Moshe Y. Vardi, Mihalis Yannakakis |
| 1999 | ICALP | Communicating Hierarchical State Machines. | Rajeev Alur, Sampath Kannan, Mihalis Yannakakis |
| 1999 | SODA | A Convex Relaxation for the Asymmetric TSP. | Santosh S. Vempala, Mihalis Yannakakis |
| 1999 | STOC | Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. | Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis |
| 1998 | CSL | Testing for Finite State Systems. | Mihalis Yannakakis, David Lee |
| 1998 | FORTE | Protocol Feature Interactions. | Thomas F. La Porta, David Lee, Yow-Jian Lin, Mihalis Yannakakis |
| 1998 | RECOMB | On the complexity of protein folding (abstract). | Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis |
| 1998 | STOC | On the Complexity of Protein Folding (Extended Abstract). | Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis |
| 1997 | CSL | Existence of Reduction Hierarchies. | Orna Kupferman, Robert P. Kurshan, Mihalis Yannakakis |
| 1997 | PODS | On the Complexity of Database Queries. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1996 | ICALP | Searching a Fixed Graph. | Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis |
| 1996 | ICNP | Optimization problems from feature testing of communication protocols. | David Lee, Mihalis Yannakakis |
| 1995 | FOCS | Perspectives on Database Theory. | Mihalis Yannakakis |
| 1995 | STOC | Distinguishing tests for nondeterministic and probabilistic machines. | Rajeev Alur, Costas Courcoubetis, Mihalis Yannakakis |
| 1994 | CIAC | Some Open Problems in Approximation. | Mihalis Yannakakis |
| 1994 | ICALP | Multiway Cuts in Directed and Node Weighted Graphs. | Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis |
| 1994 | STOC | On complexity as bounded rationality (extended abstract). | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1993 | CAV | An Efficient Algorithm for Minimizing Real-time Transition Systems. | Mihalis Yannakakis, David Lee |
| 1993 | ICALP | Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover. | Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis |
| 1993 | ICALP | The Approximation of Maximum Subgraph Problems. | Carsten Lund, Mihalis Yannakakis |
| 1993 | ISAAC | Recent Developments on the Approximability of Combinatorial Problems. | Mihalis Yannakakis |
| 1993 | STOC | Approximate max-flow min-(multi)cut theorems and their applications. | Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis |
| 1993 | STOC | On the hardness of approximating minimization problems. | Carsten Lund, Mihalis Yannakakis |
| 1993 | STOC | Linear programming without the matrix. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1992 | CAV | Timing Verification by Successive Approximation. | Rajeev Alur, Alon Itai, Robert P. Kurshan, Mihalis Yannakakis |
| 1992 | ICALP | Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract). | Vijay V. Vazirani, Mihalis Yannakakis |
| 1992 | PODS | Tie-Breaking Semantics and Structural Totality. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1992 | SODA | On the Approximation of Maximum Satisfiability. | Mihalis Yannakakis |
| 1992 | STOC | The Complexity of Multiway Cuts (Extended Abstract) | Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis |
| 1992 | STOC | Online Minimization of Transition Systems (Extended Abstract) | David Lee, Mihalis Yannakakis |
| 1991 | PODC | On the Value of Information in Distributed Decision-Making (Extended Abstract). | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1991 | PODS | On Datalog vs. Polynomial Time. | Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis |
| 1991 | STOC | Linear Approximation of Shortest Superstrings | Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis |
| 1991 | STOC | Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study | Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis |
| 1991 | STOC | Testing Finite State Machines (Extended Abstract) | Mihalis Yannakakis, David Lee |
| 1990 | CAV | Memory Efficient Algorithms for the Verification of Temporal Properties. | Costas Courcoubetis, Moshe Y. Vardi, Pierre Wolper, Mihalis Yannakakis |
| 1990 | ICALP | Markov Decision Processes and Regular Events (Extended Abstract). | Costas Courcoubetis, Mihalis Yannakakis |
| 1990 | PODS | Graph-Theoretic Methods in Database Theory. | Mihalis Yannakakis |
| 1990 | SIGMOD | The Input/Output Complexity of Transitive Closure. | Jeffrey D. Ullman, Mihalis Yannakakis |
| 1990 | STOC | On the Complexity of Local Search (Extended Abstract) | Christos H. Papadimitriou, Alejandro A. Schffer, Mihalis Yannakakis |
| 1990 | STACS | The Analysis of Local Search Problems and Their Heuristics. | Mihalis Yannakakis |
| 1990 | SPAA | High-Probability Parallel Transitive Closure Algorithms. | Jeffrey D. Ullman, Mihalis Yannakakis |
| 1989 | ICALP | Shortest Paths Without a Map. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | FOCS | Verifying Temporal Properties of Finite-State Probabilistic Programs | Costas Courcoubetis, Mihalis Yannakakis |
| 1988 | ICALP | Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs. | Vijay V. Vazirani, Mihalis Yannakakis |
| 1988 | STOC | Optimization, Approximation, and Complexity Classes (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | STOC | Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | STOC | Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract) | Mihalis Yannakakis |
| 1986 | PODS | Deleting Completed Transactions. | Thanasis Hadzilacos, Mihalis Yannakakis |
| 1986 | STOC | Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract) | Mihalis Yannakakis |
| 1985 | FOCS | How Easy Is Local Search? (Extended Abstract) | David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis |
| 1985 | PODS | The Complexity of Reliable Concurrency Control. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1985 | PODS | Deadlock-Freedom (and Safety) of Transactions in a Distributed Database. | Ouri Wolfson, Mihalis Yannakakis |
| 1984 | PODS | Querying Weak Instances. | Mihalis Yannakakis |
| 1984 | STOC | On Monotone Formulae with Restricted Depth (Preliminary Version) | Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, Mihalis Yannakakis |
| 1983 | FOCS | A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract) | Mihalis Yannakakis |
| 1983 | ICALP | Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract). | Mihalis Yannakakis, Paris C. Kanellakis, Stavros S. Cosmadakis, Christos H. Papadimitriou |
| 1983 | STOC | On Notions of Information Transfer in VLSI Circuits | Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis |
| 1982 | PODS | Independent Database Schemas. | Marc H. Graham, Mihalis Yannakakis |
| 1982 | STOC | The Complexity of Facets (and Some Facets of Complexity) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1981 | FOCS | Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1981 | STOC | Properties of Acyclic Database Schemes | Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis |
| 1981 | STOC | Issues of Correctness in Database Concurrency Control by Locking | Mihalis Yannakakis |
| 1981 | VLDB | Algorithms for Acyclic Database Schemes | Mihalis Yannakakis |
| 1980 | FOCS | On a Class of Totally Unimodular Matrices | Mihalis Yannakakis |
| 1980 | FOCS | Algebraic Dependencies (Extended Abstract) | Mihalis Yannakakis, Christos H. Papadimitriou |
| 1979 | FOCS | Modeling Communications Protocols by Automata | Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis |
| 1979 | FOCS | Locking Policies: Safety and Freedom from Deadlock | Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung |
| 1979 | ICALP | The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1978 | STOC | Node- and Edge-Deletion NP-Complete Problems | Mihalis Yannakakis |
| 1978 | VLDB | Equivalence among Relational Expressions with the Union and Difference Operation. | Yehoshua Sagiv, Mihalis Yannakakis |