Mihalis Yannakakis

ORCID

Publication Activity (10 Years)

Years Active: 1978-2024
Publications (10 Years): 52

Top Venues

CoRR

SODA

STOC

Electron. Colloquium Comput. Complex.

Publications

Xi Chen, Yuhao Li, Mihalis Yannakakis
Computing a Fixed Point of Contraction Maps in Polynomial Queries. Electron. Colloquium Comput. Complex. (2024)
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis
Smoothed Complexity of SWAP in Local Graph Partitioning. SODA (2024)
Xi Chen, Yuhao Li, Mihalis Yannakakis
Computing a Fixed Point of Contraction Maps in Polynomial Queries. STOC (2024)
Xi Chen, Yuhao Li, Mihalis Yannakakis
Computing a Fixed Point of Contraction Maps in Polynomial Queries. CoRR (2024)
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis
Smoothed Complexity of SWAP in Local Graph Partitioning. CoRR (2023)
Xi Chen, Yuhao Li, Mihalis Yannakakis
Reducing Tarski to Unique Tarski (In the Black-Box Model). CCC (2023)
Amol Pasarkar, Christos H. Papadimitriou, Mihalis Yannakakis
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. ITCS (2023)
Miranda Christ, Mihalis Yannakakis
The Smoothed Complexity of Policy Iteration for Markov Decision Processes. STOC (2023)
Xi Chen, Yuhao Li, Mihalis Yannakakis
Reducing Tarski to Unique Tarski (in the Black-box Model). Electron. Colloquium Comput. Complex. (2023)
Daniel Mitropolsky, Adiba Ejaz, Mirah Shi, Mihalis Yannakakis, Christos H. Papadimitriou
Center-Embedding and Constituency in the Brain and a New Characterization of Context-Free Languages. CoRR (2022)
Mihalis Yannakakis
Technical Perspective: Structure and Complexity of Bag Consistency. SIGMOD Rec. 51 (1) (2022)
Amol Pasarkar, Mihalis Yannakakis, Christos H. Papadimitriou
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP. CoRR (2022)
Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis
Computational Hardness of the Hylland-Zeckhauser Scheme. SODA (2022)
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer. SIAM J. Comput. 51 (3) (2022)
Miranda Christ, Mihalis Yannakakis
The Smoothed Complexity of Policy Iteration for Markov Decision Processes. CoRR (2022)
Christos Harilaos Papadimitriou, Kiran Vodrahalli, Mihalis Yannakakis
The Platform Design Problem. WINE (2021)
Huazhe Wang, Puneet Sharma, Faraz Ahmed, Joon-Myung Kang, Chen Qian, Mihalis Yannakakis
Epinoia: Intent Checker for Stateful Networks. ICCCN (2021)
Vijay V. Vazirani, Mihalis Yannakakis
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. ITCS (2021)
Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis
Computational Hardness of the Hylland-Zeckhauser Scheme. CoRR (2021)
Christos H. Papadimitriou, Kiran Vodrahalli, Mihalis Yannakakis
The Platform Design Problem. CoRR (2020)
Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. ITCS (2020)
Mihalis Yannakakis
Planar graphs that need four pages. J. Comb. Theory, Ser. B 145 (2020)
Mihalis Yannakakis
Planar Graphs that Need Four Pages. CoRR (2020)
Diman Zad Tootaghaj, Faraz Ahmed, Puneet Sharma, Mihalis Yannakakis
Homa: An Efficient Topology and Route Management Approach in SD-WAN Overlays. INFOCOM (2020)
Vijay V. Vazirani, Mihalis Yannakakis
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. CoRR (2020)
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
Doubly Balanced Connected Graph Partitioning. ACM Trans. Algorithms 16 (2) (2020)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations. Math. Oper. Res. 45 (1) (2020)
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang
Smoothed complexity of local max-cut and binary max-CSP. STOC (2020)
Soo-Jin Moon, Jeffrey Helt, Yifei Yuan, Yves Bieri, Sujata Banerjee, Vyas Sekar, Wenfei Wu, Mihalis Yannakakis, Ying Zhang
Alembic: Automated Model Inference for Stateful Network Functions. NSDI (2019)
Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis
Reachability for Branching Concurrent Stochastic Games. ICALP (2019)
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang
Smoothed complexity of local Max-Cut and binary Max-CSP. CoRR (2019)
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis
The Complexity of Finding {$S$}-factors in Regular Graphs. Electron. Colloquium Comput. Complex. 26 (2019)
Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis
Recursive stochastic games with positive rewards. Theor. Comput. Sci. 777 (2019)
Mihalis Yannakakis
Fixed Point Computation Problems and Facets of Complexity (Invited Talk). ICALP (2019)
Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. CoRR (2019)
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
REACT to Cyber Attacks on Power Grids. IEEE Trans. Netw. Sci. Eng. 6 (3) (2019)
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis
The Complexity of Finding S-Factors in Regular Graphs. FSTTCS (2019)
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
REACT to Cyber-Physical Attacks on Power grids (Extended Abstract). SIGMETRICS Perform. Evaluation Rev. 46 (2) (2018)
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
The complexity of optimal multidimensional pricing for a unit-demand buyer. Games Econ. Behav. 110 (2018)
Maximilian Haas-Heger, Christos H. Papadimitriou, Mihalis Yannakakis, Garud Iyengar, Matei T. Ciocarlie
Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis. Robotics: Science and Systems (2018)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes. Inf. Comput. 261 (2018)
Maximilian Haas-Heger, Christos H. Papadimitriou, Mihalis Yannakakis, Garud Iyengar, Matei T. Ciocarlie
Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis. CoRR (2018)
Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis
Reachability for Branching Concurrent Stochastic Games. CoRR (2018)
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
Power Grid State Estimation Following a Joint Cyber and Physical Attack. IEEE Trans. Control. Netw. Syst. 5 (1) (2018)
Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer. SODA (2018)
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
REACT to Cyber Attacks on Power Grids. CoRR (2017)
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
The Complexity of Non-Monotone Markets. J. ACM 64 (3) (2017)
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
Doubly Balanced Connected Graph Partitioning. SODA (2017)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes. SIAM J. Comput. 46 (5) (2017)
Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis
On the Complexity of Bundle-Pricing and Simple Mechanisms. CoRR (2017)
Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis
How Good is the Chord Algorithm? SIAM J. Comput. 45 (3) (2016)
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
Doubly Balanced Connected Graph Partitioning. CoRR (2016)
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. FOCS (2015)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes. CoRR (2015)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes. ICALP (2) (2015)
Kousha Etessami, Mihalis Yannakakis
Recursive Markov Decision Processes and Recursive Stochastic Games. J. ACM 62 (2) (2015)
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
Joint Cyber and Physical Attacks on Power Grids: Graph Theoretical Approaches for Information Recovery. SIGMETRICS (2015)
Alistair Stewart, Kousha Etessami, Mihalis Yannakakis
Upper Bounds for Newton's Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata. J. ACM 62 (4) (2015)
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
The Complexity of Optimal Multidimensional Pricing. SODA (2014)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing. ACM Trans. Comput. Theory 6 (2) (2014)
Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis
How good is the Chord algorithm? CoRR (2013)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Stochastic Context-Free Grammars, Regular Languages, and Newton's Method. ICALP (2) (2013)
Patrice Godefroid, Mihalis Yannakakis
Analysis of Boolean Programs. TACAS (2013)
Alistair Stewart, Kousha Etessami, Mihalis Yannakakis
Upper Bounds for Newton's Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata. CAV (2013)
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
The Complexity of Optimal Multidimensional Pricing. CoRR (2013)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Stochastic Context-Free Grammars, Regular Languages, and Newton's Method CoRR (2013)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing CoRR (2013)
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
The complexity of non-monotone markets. STOC (2013)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. Electron. Colloquium Comput. Complex. 20 (2013)
Alistair Stewart, Kousha Etessami, Mihalis Yannakakis
Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata CoRR (2013)
Kousha Etessami, Mihalis Yannakakis
Model Checking of Recursive Probabilistic Systems. ACM Trans. Comput. Log. 13 (2) (2012)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars CoRR (2012)
Mihalis Yannakakis
Computation of Least Fixed Points. MFCS (2012)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars. STOC (2012)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations. ICALP (1) (2012)
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
The Complexity of Non-Monotone Markets CoRR (2012)
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations CoRR (2012)
Orna Kupferman, Yoad Lustig, Moshe Y. Vardi, Mihalis Yannakakis
Temporal Synthesis for Bounded Systems and Environments. STACS (2011)
Vijay V. Vazirani, Mihalis Yannakakis
Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM 58 (3) (2011)
Christos H. Papadimitriou, Mihalis Yannakakis
An impossibility theorem for price-adjustment mechanisms. Proc. Natl. Acad. Sci. USA 107 (5) (2010)
Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis
How Good is the Chord Algorithm?. SODA (2010)
Vijay V. Vazirani, Mihalis Yannakakis
Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities. ICS (2010)
Mihalis Yannakakis
Computation of Equilibria and Stable Solutions. SSS (2010)
Kousha Etessami, Mihalis Yannakakis
On the Complexity of Nash Equilibria and Other Fixed Points. SIAM J. Comput. 39 (6) (2010)
Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis
Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems. Perform. Evaluation 67 (9) (2010)
Ilias Diakonikolas, Mihalis Yannakakis
Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems. SIAM J. Comput. 39 (4) (2009)
Mihalis Yannakakis
Equilibria, fixed points, and complexity classes. Comput. Sci. Rev. 3 (2) (2009)
Kousha Etessami, Mihalis Yannakakis
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM 56 (1) (2009)
Mihalis Yannakakis
Computational Aspects of Equilibria. SAGT (2009)
Kousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis
Multi-Objective Model Checking of Markov Decision Processes CoRR (2008)
Mihalis Yannakakis
Equilibria, Fixed Points, and Complexity Classes CoRR (2008)
Ilias Diakonikolas, Mihalis Yannakakis
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems CoRR (2008)
Kousha Etessami, Mihalis Yannakakis
Recursive Concurrent Stochastic Games. Log. Methods Comput. Sci. 4 (4) (2008)
Kousha Etessami, Mihalis Yannakakis
Recursive Concurrent Stochastic Games CoRR (2008)
Kousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis
Multi-Objective Model Checking of Markov Decision Processes. Log. Methods Comput. Sci. 4 (4) (2008)
Mihalis Yannakakis
Automata, Probability, and Recursion. CIAA (2008)
Ilias Diakonikolas, Mihalis Yannakakis
Succinct approximate convex pareto curves. SODA (2008)
Mihalis Yannakakis
Equilibria, Fixed Points, and Complexity Classes. STACS (2008)
Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis
Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems. QEST (2008)
Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis
Recursive Stochastic Games with Positive Rewards. ICALP (1) (2008)

Mihalis Yannakakis.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Mihalis Yannakakis