default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMihalis Yannakakis
Person information
- affiliation: Columbia University, New York City, USA
- award (2005): Knuth Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c148]Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis:
Smoothed Complexity of SWAP in Local Graph Partitioning. SODA 2024: 5057-5083- [c147]Xi Chen
, Yuhao Li, Mihalis Yannakakis:
Computing a Fixed Point of Contraction Maps in Polynomial Queries. STOC 2024: 1364-1373 - [i34]Xi Chen, Yuhao Li, Mihalis Yannakakis:
Computing a Fixed Point of Contraction Maps in Polynomial Queries. CoRR abs/2403.19911 (2024) - [i33]Rashida Hakim, Ana-Andreea Stoica, Christos H. Papadimitriou, Mihalis Yannakakis:
The Fairness-Quality Trade-off in Clustering. CoRR abs/2408.10002 (2024) - [i32]Xi Chen, Yuhao Li, Mihalis Yannakakis:
Computing a Fixed Point of Contraction Maps in Polynomial Queries. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c146]Xi Chen, Yuhao Li, Mihalis Yannakakis:
Reducing Tarski to Unique Tarski (In the Black-Box Model). CCC 2023: 21:1-21:23 - [c145]Amol Pasarkar, Christos H. Papadimitriou, Mihalis Yannakakis:
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. ITCS 2023: 88:1-88:20 - [c144]Miranda Christ, Mihalis Yannakakis:
The Smoothed Complexity of Policy Iteration for Markov Decision Processes. STOC 2023: 1890-1903 - [i31]Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis:
Smoothed Complexity of SWAP in Local Graph Partitioning. CoRR abs/2305.15804 (2023) - [i30]Xi Chen, Yuhao Li, Mihalis Yannakakis:
Reducing Tarski to Unique Tarski (in the Black-box Model). Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j110]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): 492-548 (2022) - [j109]Mihalis Yannakakis:
Technical Perspective: Structure and Complexity of Bag Consistency. SIGMOD Rec. 51(1): 77 (2022) - [c143]Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis:
Computational Hardness of the Hylland-Zeckhauser Scheme. SODA 2022: 2253-2268 - [i29]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 abs/2206.13217 (2022) - [i28]Amol Pasarkar, Mihalis Yannakakis, Christos H. Papadimitriou:
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP. CoRR abs/2209.07625 (2022) - [i27]Miranda Christ, Mihalis Yannakakis:
The Smoothed Complexity of Policy Iteration for Markov Decision Processes. CoRR abs/2212.00083 (2022) - 2021
- [c142]Huazhe Wang, Puneet Sharma, Faraz Ahmed, Joon-Myung Kang, Chen Qian, Mihalis Yannakakis:
Epinoia: Intent Checker for Stateful Networks. ICCCN 2021: 1-9 - [c141]Vijay V. Vazirani, Mihalis Yannakakis:
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. ITCS 2021: 59:1-59:19 - [c140]Christos Harilaos Papadimitriou, Kiran Vodrahalli, Mihalis Yannakakis:
The Platform Design Problem. WINE 2021: 317-333 - [i26]Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis:
Computational Hardness of the Hylland-Zeckhauser Scheme. CoRR abs/2107.05746 (2021) - 2020
- [j108]Mihalis Yannakakis:
Planar graphs that need four pages. J. Comb. Theory B 145: 241-263 (2020) - [j107]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): 34-62 (2020) - [j106]Saleh Soltan, Mihalis Yannakakis, Gil Zussman:
Doubly Balanced Connected Graph Partitioning. ACM Trans. Algorithms 16(2): 20:1-20:24 (2020) - [c139]Diman Zad Tootaghaj, Faraz Ahmed, Puneet Sharma, Mihalis Yannakakis:
Homa: An Efficient Topology and Route Management Approach in SD-WAN Overlays. INFOCOM 2020: 2351-2360 - [c138]Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis:
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. ITCS 2020: 18:1-18:19 - [c137]Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang:
Smoothed complexity of local max-cut and binary max-CSP. STOC 2020: 1052-1065 - [i25]Vijay V. Vazirani, Mihalis Yannakakis:
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. CoRR abs/2004.01348 (2020) - [i24]Mihalis Yannakakis:
Planar Graphs that Need Four Pages. CoRR abs/2005.14111 (2020) - [i23]Christos H. Papadimitriou, Kiran Vodrahalli, Mihalis Yannakakis:
The Platform Design Problem. CoRR abs/2009.06117 (2020)
2010 – 2019
- 2019
- [j105]Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis:
Recursive stochastic games with positive rewards. Theor. Comput. Sci. 777: 308-328 (2019) - [j104]Saleh Soltan, Mihalis Yannakakis, Gil Zussman:
REACT to Cyber Attacks on Power Grids. IEEE Trans. Netw. Sci. Eng. 6(3): 459-473 (2019) - [c136]Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis:
The Complexity of Finding S-Factors in Regular Graphs. FSTTCS 2019: 21:1-21:12 - [c135]Mihalis Yannakakis:
Fixed Point Computation Problems and Facets of Complexity (Invited Talk). ICALP 2019: 5:1-5:1 - [c134]Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis:
Reachability for Branching Concurrent Stochastic Games. ICALP 2019: 115:1-115:14 - [c133]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: 699-718 - [i22]Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis:
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. CoRR abs/1909.03210 (2019) - [i21]Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang:
Smoothed complexity of local Max-Cut and binary Max-CSP. CoRR abs/1911.10381 (2019) - [i20]Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis:
The Complexity of Finding S-factors in Regular Graphs. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j103]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: 139-164 (2018) - [j102]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: 355-382 (2018) - [j101]Saleh Soltan, Mihalis Yannakakis, Gil Zussman:
REACT to Cyber-Physical Attacks on Power grids (Extended Abstract). SIGMETRICS Perform. Evaluation Rev. 46(2): 50-51 (2018) - [j100]Saleh Soltan, Mihalis Yannakakis, Gil Zussman:
Power Grid State Estimation Following a Joint Cyber and Physical Attack. IEEE Trans. Control. Netw. Syst. 5(1): 499-512 (2018) - [c132]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 - [c131]Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis:
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer. SODA 2018: 2036-2049 - [i19]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 abs/1806.01384 (2018) - [i18]Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis:
Reachability for Branching Concurrent Stochastic Games. CoRR abs/1806.03907 (2018) - 2017
- [j99]Xi Chen, Dimitris Paparas, Mihalis Yannakakis:
The Complexity of Non-Monotone Markets. J. ACM 64(3): 20:1-20:56 (2017) - [j98]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes. SIAM J. Comput. 46(5): 1515-1553 (2017) - [c130]Saleh Soltan, Mihalis Yannakakis, Gil Zussman:
Doubly Balanced Connected Graph Partitioning. SODA 2017: 1939-1950 - [i17]Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis:
On the Complexity of Bundle-Pricing and Simple Mechanisms. CoRR abs/1702.07032 (2017) - [i16]Saleh Soltan, Mihalis Yannakakis, Gil Zussman:
REACT to Cyber Attacks on Power Grids. CoRR abs/1709.06934 (2017) - 2016
- [j97]Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis:
How Good is the Chord Algorithm? SIAM J. Comput. 45(3): 811-858 (2016) - [i15]Saleh Soltan, Mihalis Yannakakis, Gil Zussman:
Doubly Balanced Connected Graph Partitioning. CoRR abs/1607.06509 (2016) - 2015
- [j96]Kousha Etessami, Mihalis Yannakakis:
Recursive Markov Decision Processes and Recursive Stochastic Games. J. ACM 62(2): 11:1-11:69 (2015) - [j95]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): 30:1-30:33 (2015) - [c129]Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. FOCS 2015: 1464-1479 - [c128]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: 184-196 - [c127]Saleh Soltan, Mihalis Yannakakis, Gil Zussman:
Joint Cyber and Physical Attacks on Power Grids: Graph Theoretical Approaches for Information Recovery. SIGMETRICS 2015: 361-374 - [i14]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes. CoRR abs/1502.05533 (2015) - 2014
- [j94]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): 9:1-9:23 (2014) - [c126]Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
The Complexity of Optimal Multidimensional Pricing. SODA 2014: 1319-1328 - 2013
- [c125]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: 495-510 - [c124]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Stochastic Context-Free Grammars, Regular Languages, and Newton's Method. ICALP (2) 2013: 199-211 - [c123]Xi Chen, Dimitris Paparas, Mihalis Yannakakis:
The complexity of non-monotone markets. STOC 2013: 181-190 - [c122]Patrice Godefroid, Mihalis Yannakakis:
Analysis of Boolean Programs. TACAS 2013: 214-229 - [i13]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 abs/1302.3741 (2013) - [i12]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Stochastic Context-Free Grammars, Regular Languages, and Newton's Method. CoRR abs/1302.6411 (2013) - [i11]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. CoRR abs/1304.5429 (2013) - [i10]Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis:
How good is the Chord algorithm? CoRR abs/1309.7084 (2013) - [i9]Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
The Complexity of Optimal Multidimensional Pricing. CoRR abs/1311.2138 (2013) - [i8]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. TR13 (2013) - 2012
- [j93]Kousha Etessami, Mihalis Yannakakis:
Model Checking of Recursive Probabilistic Systems. ACM Trans. Comput. Log. 13(2): 12:1-12:40 (2012) - [c121]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations. ICALP (1) 2012: 314-326 - [c120]Mihalis Yannakakis:
Computation of Least Fixed Points. MFCS 2012: 63 - [c119]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars. STOC 2012: 579-588 - [i7]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars. CoRR abs/1201.2374 (2012) - [i6]Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations. CoRR abs/1202.4798 (2012) - [i5]Xi Chen, Dimitris Paparas, Mihalis Yannakakis:
The Complexity of Non-Monotone Markets. CoRR abs/1211.4918 (2012) - 2011
- [j92]Vijay V. Vazirani, Mihalis Yannakakis:
Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM 58(3): 10:1-10:25 (2011) - [c118]Orna Kupferman, Yoad Lustig, Moshe Y. Vardi, Mihalis Yannakakis:
Temporal Synthesis for Bounded Systems and Environments. STACS 2011: 615-626 - 2010
- [j91]Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis:
Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems. Perform. Evaluation 67(9): 837-857 (2010) - [j90]Christos H. Papadimitriou, Mihalis Yannakakis:
An impossibility theorem for price-adjustment mechanisms. Proc. Natl. Acad. Sci. USA 107(5): 1854-1859 (2010) - [j89]Kousha Etessami, Mihalis Yannakakis:
On the Complexity of Nash Equilibria and Other Fixed Points. SIAM J. Comput. 39(6): 2531-2597 (2010) - [c117]Vijay V. Vazirani, Mihalis Yannakakis:
Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities. ICS 2010: 156-165 - [c116]Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis:
How Good is the Chord Algorithm?. SODA 2010: 978-991 - [c115]Mihalis Yannakakis:
Computation of Equilibria and Stable Solutions. SSS 2010: 2
2000 – 2009
- 2009
- [j88]Mihalis Yannakakis:
Equilibria, fixed points, and complexity classes. Comput. Sci. Rev. 3(2): 71-85 (2009) - [j87]Kousha Etessami, Mihalis Yannakakis:
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM 56(1): 1:1-1:66 (2009) - [j86]Ilias Diakonikolas, Mihalis Yannakakis:
Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems. SIAM J. Comput. 39(4): 1340-1371 (2009) - [c114]Mihalis Yannakakis:
Computational Aspects of Equilibria. SAGT 2009: 2-13 - 2008
- [j85]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) - [j84]Kousha Etessami, Mihalis Yannakakis:
Recursive Concurrent Stochastic Games. Log. Methods Comput. Sci. 4(4) (2008) - [c113]Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis:
Recursive Stochastic Games with Positive Rewards. ICALP (1) 2008: 711-723 - [c112]Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis:
Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems. QEST 2008: 243-253 - [c111]Ilias Diakonikolas, Mihalis Yannakakis:
Succinct approximate convex pareto curves. SODA 2008: 74-83 - [c110]Mihalis Yannakakis:
Equilibria, Fixed Points, and Complexity Classes. STACS 2008: 19-38 - [c109]Mihalis Yannakakis:
Automata, Probability, and Recursion. CIAA 2008: 23-32 - [i4]Mihalis Yannakakis:
Equilibria, Fixed Points, and Complexity Classes. CoRR abs/0802.2831 (2008) - [i3]Ilias Diakonikolas, Mihalis Yannakakis:
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems. CoRR abs/0805.2646 (2008) - [i2]Kousha Etessami, Mihalis Yannakakis:
Recursive Concurrent Stochastic Games. CoRR abs/0810.3581 (2008) - [i1]Kousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis:
Multi-Objective Model Checking of Markov Decision Processes. CoRR abs/0810.5728 (2008) - 2007
- [c108]Ilias Diakonikolas, Mihalis Yannakakis:
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems. APPROX-RANDOM 2007: 74-88 - [c107]Kousha Etessami, Mihalis Yannakakis:
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). FOCS 2007: 113-123 - [c106]Kousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis:
Multi-objective Model Checking of Markov Decision Processes. TACAS 2007: 50-65 - 2006
- [j83]Alex Groce, Doron A. Peled, Mihalis Yannakakis:
Adaptive Model Checking. Log. J. IGPL 14(5): 729-744 (2006) - [c105]Mihalis Yannakakis:
Analysis of Recursive Probabilistic Models. ATVA 2006: 1-5 - [c104]Kousha Etessami, Mihalis Yannakakis:
Recursive Concurrent Stochastic Games. ICALP (2) 2006: 324-335 - [c103]Mihalis Yannakakis:
Recursion and Probability. IFIP TCS 2006: 13 - [c102]Guoqiang Shu, David Lee, Mihalis Yannakakis:
A note on broadcast encryption key management with applications to large scale emergency alert systems. IPDPS 2006 - [c101]Kousha Etessami, Mihalis Yannakakis:
Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games. STACS 2006: 634-645 - [c100]Mihalis Yannakakis:
Succinct Approximation of Trade-Off Curves. WINE 2006: 149 - 2005
- [j82]Rajeev Alur, Kousha Etessami, Mihalis Yannakakis:
Realizability and verification of MSC graphs. Theor. Comput. Sci. 331(1): 97-114 (2005) - [j81]Sergei Vassilvitskii, Mihalis Yannakakis:
Efficiently computing succinct trade-off curves. Theor. Comput. Sci. 348(2-3): 334-356 (2005) - [j80]Rajeev Alur, Michael Benedikt, Kousha Etessami, Patrice Godefroid, Thomas W. Reps, Mihalis Yannakakis:
Analysis of recursive state machines. ACM Trans. Program. Lang. Syst. 27(4): 786-818 (2005) - [c99]Kousha Etessami, Mihalis Yannakakis:
Recursive Markov Decision Processes and Recursive Stochastic Games. ICALP 2005: 891-903 - [c98]Kousha Etessami, Mihalis Yannakakis:
Probability and Recursion. ISAAC 2005: 2-4 - [c97]Mihalis Yannakakis, Kousha Etessami:
Checking LTL Properties of Recursive Markov Chains. QEST 2005: 155-165 - [c96]Damon Mosk-Aoyama, Mihalis Yannakakis:
Testing hierarchical systems. SODA 2005: 1126-1135 - [c95]Kousha Etessami, Mihalis Yannakakis:
Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. STACS 2005: 340-352 - [c94]Kousha Etessami, Mihalis Yannakakis:
Algorithmic Verification of Recursive Probabilistic State Machines. TACAS 2005: 253-270 - 2004
- [j79]Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis:
Multiway cuts in node weighted graphs. J. Algorithms 50(