 | 2009 |
|---|
| 197 |       | Mihalis Yannakakis:
Computational Aspects of Equilibria.
SAGT 2009: 2-13 |
| 196 | | Mihalis Yannakakis:
Equilibria, fixed points, and complexity classes.
Computer Science Review 3(2): 71-85 (2009) |
| 195 | | Kousha Etessami,
Mihalis Yannakakis:
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations.
J. ACM 56(1): (2009) |
| 194 | | Ilias Diakonikolas,
Mihalis Yannakakis:
Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems.
SIAM J. Comput. 39(4): 1340-1371 (2009) |
| 2008 |
|---|
| 193 | | Mihalis Yannakakis:
Automata, Probability, and Recursion.
CIAA 2008: 23-32 |
| 192 | | Kousha Etessami,
Dominik Wojtczak,
Mihalis Yannakakis:
Recursive Stochastic Games with Positive Rewards.
ICALP (1) 2008: 711-723 |
| 191 | | Kousha Etessami,
Dominik Wojtczak,
Mihalis Yannakakis:
Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems.
QEST 2008: 243-253 |
| 190 | | Ilias Diakonikolas,
Mihalis Yannakakis:
Succinct approximate convex pareto curves.
SODA 2008: 74-83 |
| 189 | | Mihalis Yannakakis:
Equilibria, Fixed Points, and Complexity Classes.
STACS 2008: 19-38 |
| 188 | | Mihalis Yannakakis:
Equilibria, Fixed Points, and Complexity Classes
CoRR abs/0802.2831: (2008) |
| 187 | | Ilias Diakonikolas,
Mihalis Yannakakis:
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
CoRR abs/0805.2646: (2008) |
| 186 | | Kousha Etessami,
Mihalis Yannakakis:
Recursive Concurrent Stochastic Games
CoRR abs/0810.3581: (2008) |
| 185 | | Kousha Etessami,
Marta Z. Kwiatkowska,
Moshe Y. Vardi,
Mihalis Yannakakis:
Multi-Objective Model Checking of Markov Decision Processes
CoRR abs/0810.5728: (2008) |
| 184 | | Kousha Etessami,
Marta Z. Kwiatkowska,
Moshe Y. Vardi,
Mihalis Yannakakis:
Multi-Objective Model Checking of Markov Decision Processes.
Logical Methods in Computer Science 4(4): (2008) |
| 183 | | Kousha Etessami,
Mihalis Yannakakis:
Recursive Concurrent Stochastic Games.
Logical Methods in Computer Science 4(4): (2008) |
| 2007 |
|---|
| 182 | | Ilias Diakonikolas,
Mihalis Yannakakis:
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems.
APPROX-RANDOM 2007: 74-88 |
| 181 | | Kousha Etessami,
Mihalis Yannakakis:
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract).
FOCS 2007: 113-123 |
| 180 | | Kousha Etessami,
Marta Z. Kwiatkowska,
Moshe Y. Vardi,
Mihalis Yannakakis:
Multi-objective Model Checking of Markov Decision Processes.
TACAS 2007: 50-65 |
| 2006 |
|---|
| 179 | | Mihalis Yannakakis:
Analysis of Recursive Probabilistic Models.
ATVA 2006: 1-5 |
| 178 | | Kousha Etessami,
Mihalis Yannakakis:
Recursive Concurrent Stochastic Games.
ICALP (2) 2006: 324-335 |
| 177 | | Mihalis Yannakakis:
Recursion and Probability.
IFIP TCS 2006: 13 |
| 176 | | Guoqiang Shu,
David Lee,
Mihalis Yannakakis:
A note on broadcast encryption key management with applications to large scale emergency alert systems.
IPDPS 2006 |
| 175 | | Kousha Etessami,
Mihalis Yannakakis:
Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games.
STACS 2006: 634-645 |
| 174 | | Mihalis Yannakakis:
Succinct Approximation of Trade-Off Curves.
WINE 2006: 149 |
| 173 | | Alex Groce,
Doron Peled,
Mihalis Yannakakis:
Adaptive Model Checking.
Logic Journal of the IGPL 14(5): 729-744 (2006) |
| 2005 |
|---|
| 172 | | Kousha Etessami,
Mihalis Yannakakis:
Recursive Markov Decision Processes and Recursive Stochastic Games.
ICALP 2005: 891-903 |
| 171 | | Kousha Etessami,
Mihalis Yannakakis:
Probability and Recursion.
ISAAC 2005: 2-4 |
| 170 | | Mihalis Yannakakis,
Kousha Etessami:
Checking LTL Properties of Recursive Markov Chains.
QEST 2005: 155-165 |
| 169 | | Damon Mosk-Aoyama,
Mihalis Yannakakis:
Testing hierarchical systems.
SODA 2005: 1126-1135 |
| 168 | | Kousha Etessami,
Mihalis Yannakakis:
Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations.
STACS 2005: 340-352 |
| 167 | | Kousha Etessami,
Mihalis Yannakakis:
Algorithmic Verification of Recursive Probabilistic State Machines.
TACAS 2005: 253-270 |
| 166 | | 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) |
| 165 | | Rajeev Alur,
Kousha Etessami,
Mihalis Yannakakis:
Realizability and verification of MSC graphs.
Theor. Comput. Sci. 331(1): 97-114 (2005) |
| 164 | | Sergei Vassilvitskii,
Mihalis Yannakakis:
Efficiently computing succinct trade-off curves.
Theor. Comput. Sci. 348(2-3): 334-356 (2005) |
| 2004 |
|---|
| 163 | | Sergei Vassilvitskii,
Mihalis Yannakakis:
Efficiently Computing Succinct Trade-Off Curves.
ICALP 2004: 1201-1213 |
| 162 | | Mihalis Yannakakis:
Testing, Optimizaton, and Games.
ICALP 2004: 28-45 |
| 161 | | Mihalis Yannakakis:
Testing, Optimizaton, and Games.
LICS 2004: 78-88 |
| 160 | | David Lee,
Christine Liu,
Mihalis Yannakakis:
Protocol System Integration, Interface and Interoperability.
OPODIS 2004: 1-19 |
| 159 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Multiway cuts in node weighted graphs.
J. Algorithms 50(1): 49-61 (2004) |
| 158 | | Sampath Kannan,
Mihalis Yannakakis:
Guest Editors' foreword.
J. Comput. Syst. Sci. 68(2): 237 (2004) |
| 2003 |
|---|
| 157 | | Rajeev Alur,
Swarat Chaudhuri,
Kousha Etessami,
Sudipto Guha,
Mihalis Yannakakis:
Compression of Partially Ordered Strings.
CONCUR 2003: 42-56 |
| 156 | | Rajeev Alur,
Kousha Etessami,
Mihalis Yannakakis:
Inference of Message Sequence Charts.
IEEE Trans. Software Eng. 29(7): 623-633 (2003) |
| 155 | | Venkatesan Guruswami,
Sanjeev Khanna,
Rajmohan Rajaraman,
F. Bruce Shepherd,
Mihalis Yannakakis:
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems.
J. Comput. Syst. Sci. 67(3): 473-496 (2003) |
| 2002 |
|---|
| 154 | | Alex Groce,
Doron Peled,
Mihalis Yannakakis:
AMC: An Adaptive Model Checker.
CAV 2002: 521-525 |
| 153 | | Mihalis Yannakakis:
Testing and Checking of Finite State Systems.
LATIN 2002: 14 |
| 152 | | Alex Groce,
Doron Peled,
Mihalis Yannakakis:
Adaptive Model Checking.
TACAS 2002: 357-370 |
| 151 | | David Lee,
Mihalis Yannakakis:
Closed Partition Lattice and Machine Decomposition.
IEEE Trans. Computers 51(2): 216-228 (2002) |
| 150 |  | Doron Peled,
Moshe Y. Vardi,
Mihalis Yannakakis:
Black Box Checking.
Journal of Automata, Languages and Combinatorics 7(2): 225-246 (2002) |
| 2001 |
|---|
| 149 | | Rajeev Alur,
Kousha Etessami,
Mihalis Yannakakis:
Analysis of Recursive State Machines.
CAV 2001: 207-220 |
| 148 | | Rajeev Alur,
Kousha Etessami,
Mihalis Yannakakis:
Realizability and Verification of MSC Graphs.
ICALP 2001: 797-808 |
| 147 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Multiobjective Query Optimization.
PODS 2001 |
| 146 | | Mihalis Yannakakis:
Approximation of Multiobjective Optimization Problems.
WADS 2001: 1 |
| 145 | | Rajeev Alur,
Mihalis Yannakakis:
Model checking of hierarchical state machines.
ACM Trans. Program. Lang. Syst. 23(3): 273-303 (2001) |
| 2000 |
|---|
| 144 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On the Approximability of Trade-offs and Optimal Access of Web Sources.
FOCS 2000: 86-92 |
| 143 | | Kousha Etessami,
Mihalis Yannakakis:
From Rule-based to Automata-based Testing.
FORTE 2000: 53-68 |
| 142 | | Rajeev Alur,
Kousha Etessami,
Mihalis Yannakakis:
Inference of message sequence charts.
ICSE 2000: 304-313 |
| 141 | | Mihalis Yannakakis:
Hierarchical State Machines.
IFIP TCS 2000: 315-330 |
| 140 | | Edward G. Coffman Jr.,
Costas Courcoubetis,
M. R. Garey,
David S. Johnson,
Peter W. Shor,
Richard R. Weber,
Mihalis Yannakakis:
Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.
SIAM J. Discrete Math. 13(3): 384-402 (2000) |
| 139 | | Kenneth A. Ross,
Charu C. Aggarwal,
Alfons Kemper,
Sunita Sarawagi,
S. Sudarshan,
Mihalis Yannakakis:
Reminiscences on Influential Papers.
SIGMOD Record 29(3): 52-54 (2000) |
| 1999 |
|---|
| 138 | | Rajeev Alur,
Mihalis Yannakakis:
Model Checking of Message Sequence Charts.
CONCUR 1999: 114-129 |
| 137 | | Doron Peled,
Moshe Y. Vardi,
Mihalis Yannakakis:
Black Box Checking.
FORTE 1999: 225-240 |
| 136 | | Rajeev Alur,
Sampath Kannan,
Mihalis Yannakakis:
Communicating Hierarchical State Machines.
ICALP 1999: 169-178 |
| 135 | | Santosh Vempala,
Mihalis Yannakakis:
A Convex Relaxation for the Asymmetric TSP.
SODA 1999: 975-976 |
| 134 | | Venkatesan Guruswami,
Sanjeev Khanna,
Rajmohan Rajaraman,
F. Bruce Shepherd,
Mihalis Yannakakis:
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
STOC 1999: 19-28 |
| 133 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On the Complexity of Database Queries.
J. Comput. Syst. Sci. 58(3): 407-427 (1999) |
| 1998 |
|---|
| 132 | | Mihalis Yannakakis,
David Lee:
Testing for Finite State Systems.
CSL 1998: 29-44 |
| 131 | | Thomas F. La Porta,
David Lee,
Yow-Jian Lin,
Mihalis Yannakakis:
Protocol Feature Interactions.
FORTE 1998: 59-74 |
| 130 | | Pierluigi Crescenzi,
Deborah Goldman,
Christos H. Papadimitriou,
Antonio Piccolboni,
Mihalis Yannakakis:
On the complexity of protein folding (abstract).
RECOMB 1998: 61-62 |
| 129 | | Rajeev Alur,
Mihalis Yannakakis:
Model Checking of Hierarchical State Machines.
SIGSOFT FSE 1998: 175-188 |
| 128 | | Pierluigi Crescenzi,
Deborah Goldman,
Christos H. Papadimitriou,
Antonio Piccolboni,
Mihalis Yannakakis:
On the Complexity of Protein Folding (Extended Abstract).
STOC 1998: 597-603 |
| 127 | | Pierluigi Crescenzi,
Deborah Goldman,
Christos H. Papadimitriou,
Antonio Piccolboni,
Mihalis Yannakakis:
On the Complexity of Protein Folding.
Journal of Computational Biology 5(3): 423-466 (1998) |
| 1997 |
|---|
| 126 | | Orna Kupferman,
Robert P. Kurshan,
Mihalis Yannakakis:
Existence of Reduction Hierarchies.
CSL 1997: 327-340 |
| 125 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On the Complexity of Database Queries.
PODS 1997: 12-19 |
| 124 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees.
Algorithmica 18(1): 3-20 (1997) |
| 123 | | Mihalis Yannakakis,
David Lee:
An Efficient Algorithm for Minimizing Real-Time Transition Systems.
Formal Methods in System Design 11(2): 113-136 (1997) |
| 122 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Tie-Breaking Semantics and Structural Totality.
J. Comput. Syst. Sci. 54(1): 48-60 (1997) |
| 1996 |
|---|
| 121 | | Elias Koutsoupias,
Christos H. Papadimitriou,
Mihalis Yannakakis:
Searching a Fixed Graph.
ICALP 1996: 280-289 |
| 120 | | David Lee,
Mihalis Yannakakis:
Optimization problems from feature testing of communication protocols.
ICNP 1996: 66-75 |
| 119 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On Limited Nondeterminism and the Complexity of the V-C Dimension.
J. Comput. Syst. Sci. 53(2): 161-170 (1996) |
| 118 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.
SIAM J. Comput. 25(2): 235-251 (1996) |
| 117 | | Mihalis Yannakakis:
Perspectives on database theory.
SIGACT News 27(3): 25-49 (1996) |
| 1995 |
|---|
| 116 | | Mihalis Yannakakis:
Perspectives on Database Theory.
FOCS 1995: 224-246 |
| 115 | | Rajeev Alur,
Costas Courcoubetis,
Mihalis Yannakakis:
Distinguishing tests for nondeterministic and probabilistic machines.
STOC 1995: 363-372 |
| 114 | | Rajeev Alur,
Alon Itai,
Robert P. Kurshan,
Mihalis Yannakakis:
Timing Verification by Successive Approximation
Inf. Comput. 118(1): 142-157 (1995) |
| 113 | | Costas Courcoubetis,
Mihalis Yannakakis:
The Complexity of Probabilistic Verification.
J. ACM 42(4): 857-907 (1995) |
| 112 | | Mihalis Yannakakis,
David Lee:
Testing Finite State Machines: Fault Detection.
J. Comput. Syst. Sci. 50(2): 209-227 (1995) |
| 111 | | Foto N. Afrati,
Stavros S. Cosmadakis,
Mihalis Yannakakis:
On Datalog vs. Polynomial Time.
J. Comput. Syst. Sci. 51(2): 177-196 (1995) |
| 1994 |
|---|
| 110 | | Mihalis Yannakakis:
Some Open Problems in Approximation.
CIAC 1994: 33-39 |
| 109 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Multiway Cuts in Directed and Node Weighted Graphs.
ICALP 1994: 487-498 |
| 108 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On complexity as bounded rationality (extended abstract).
STOC 1994: 726-733 |
| 107 | | David Lee,
Mihalis Yannakakis:
Testing Finite-State Machines: State Identification and Verification.
IEEE Trans. Computers 43(3): 306-320 (1994) |
| 106 | | Avrim Blum,
Tao Jiang,
Ming Li,
John Tromp,
Mihalis Yannakakis:
Linear Approximation of Shortest Superstrings.
J. ACM 41(4): 630-647 (1994) |
| 105 | | Carsten Lund,
Mihalis Yannakakis:
On the Hardness of Approximating Minimization Problems.
J. ACM 41(5): 960-981 (1994) |
| 104 | | Mihalis Yannakakis:
On the Approximation of Maximum Satisfiability.
J. Algorithms 17(3): 475-502 (1994) |
| 103 | | Elias Dahlhaus,
David S. Johnson,
Christos H. Papadimitriou,
Paul D. Seymour,
Mihalis Yannakakis:
The Complexity of Multiterminal Cuts.
SIAM J. Comput. 23(4): 864-894 (1994) |
| 1993 |
|---|
| 102 | | Mihalis Yannakakis,
David Lee:
An Efficient Algorithm for Minimizing Real-time Transition Systems.
CAV 1993: 210-224 |
| 101 | | Carsten Lund,
Mihalis Yannakakis:
The Approximation of Maximum Subgraph Problems.
ICALP 1993: 40-51 |
| 100 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover.
ICALP 1993: 64-75 |
| 99 | | Mihalis Yannakakis:
Recent Developments on the Approximability of Combinatorial Problems.
ISAAC 1993: 363-368 |
| 98 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Linear programming without the matrix.
STOC 1993: 121-129 |
| 97 | | Carsten Lund,
Mihalis Yannakakis:
On the hardness of approximating minimization problems.
STOC 1993: 286-293 |
| 96 | | Naveen Garg,
Vijay V. Vazirani,
Mihalis Yannakakis:
Approximate max-flow min-(multi)cut theorems and their applications.
STOC 1993: 698-707 |
| 95 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract).
Structure in Complexity Theory Conference 1993: 12-18 |
| 94 | | Christos H. Papadimitriou,
Paolo Serafini,
Mihalis Yannakakis:
Computing the Throughput of a Network with Dedicated Lines.
Discrete Applied Mathematics 42(2): 271-278 (1993) |
| 1992 |
|---|
| 93 | | Rajeev Alur,
Alon Itai,
Robert P. Kurshan,
Mihalis Yannakakis:
Timing Verification by Successive Approximation.
CAV 1992: 137-150 |
| 92 | | Vijay V. Vazirani,
Mihalis Yannakakis:
Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract).
ICALP 1992: 366-377 |
| 91 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Tie-Breaking Semantics and Structural Totality.
PODS 1992: 16-22 |
| 90 | | Mihalis Yannakakis:
On the Approximation of Maximum Satisfiability.
SODA 1992: 1-9 |
| 89 | | Elias Dahlhaus,
David S. Johnson,
Christos H. Papadimitriou,
Paul D. Seymour,
Mihalis Yannakakis:
The Complexity of Multiway Cuts (Extended Abstract)
STOC 1992: 241-251 |
| 88 | | David Lee,
Mihalis Yannakakis:
Online Minimization of Transition Systems (Extended Abstract)
STOC 1992: 264-274 |
| 87 | | Costas Courcoubetis,
Moshe Y. Vardi,
Pierre Wolper,
Mihalis Yannakakis:
Memory-Efficient Algorithms for the Verification of Temporal Properties.
Formal Methods in System Design 1(2/3): 275-288 (1992) |
| 86 | | Costas Courcoubetis,
Mihalis Yannakakis:
Minimum and Maximum Delay Problems in Real-Time Systems.
Formal Methods in System Design 1(4): 385-415 (1992) |
| 1991 |
|---|
| 85 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On the Value of Information in Distributed Decision-Making (Extended Abstract).
PODC 1991: 61-64 |
| 84 | | Foto N. Afrati,
Stavros S. Cosmadakis,
Mihalis Yannakakis:
On Datalog vs. Polynomial Time.
PODS 1991: 13-25 |
| 83 | | Edward G. Coffman Jr.,
Costas Courcoubetis,
M. R. Garey,
David S. Johnson,
Lyle A. McGeoch,
Peter W. Shor,
Richard R. Weber,
Mihalis Yannakakis:
Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study
STOC 1991: 230-240 |
| 82 | | Avrim Blum,
Tao Jiang,
Ming Li,
John Tromp,
Mihalis Yannakakis:
Linear Approximation of Shortest Superstrings
STOC 1991: 328-336 |
| 81 | | Mihalis Yannakakis,
David Lee:
Testing Finite State Machines (Extended Abstract)
STOC 1991: 476-485 |
| 80 | | Jeffrey D. Ullman,
Mihalis Yannakakis:
The Input/Output Complexity of Transitive Closure.
Ann. Math. Artif. Intell. 3(2-4): 331-360 (1991) |
| 79 | | Esther M. Arkin,
Christos H. Papadimitriou,
Mihalis Yannakakis:
Modularity of Cycles and Paths in Graphs.
J. ACM 38(2): 255-274 (1991) |
| 78 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Optimization, Approximation, and Complexity Classes.
J. Comput. Syst. Sci. 43(3): 425-440 (1991) |
| 77 | | Mihalis Yannakakis:
Expressing Combinatorial Optimization Problems by Linear Programs.
J. Comput. Syst. Sci. 43(3): 441-466 (1991) |
| 76 | | Jeffrey D. Ullman,
Mihalis Yannakakis:
High-Probability Parallel Transitive-Closure Algorithms.
SIAM J. Comput. 20(1): 100-125 (1991) |
| 75 | | Alejandro A. Schäffer,
Mihalis Yannakakis:
Simple Local Search Problems That are Hard to Solve.
SIAM J. Comput. 20(1): 56-87 (1991) |
| 74 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Shortest Paths Without a Map.
Theor. Comput. Sci. 84(1): 127-150 (1991) |
| 1990 |
|---|
| 73 | | Costas Courcoubetis,
Moshe Y. Vardi,
Pierre Wolper,
Mihalis Yannakakis:
Memory Efficient Algorithms for the Verification of Temporal Properties.
CAV 1990: 233-242 |
| 72 | | Costas Courcoubetis,
Mihalis Yannakakis:
Markov Decision Processes and Regular Events (Extended Abstract).
ICALP 1990: 336-349 |
| 71 | | Mihalis Yannakakis:
Graph-Theoretic Methods in Database Theory.
PODS 1990: 230-242 |
| 70 | | Jeffrey D. Ullman,
Mihalis Yannakakis:
The Input/Output Complexity of Transitive Closure.
SIGMOD Conference 1990: 44-53 |
| 69 | | Jeffrey D. Ullman,
Mihalis Yannakakis:
High-Probability Parallel Transitive Closure Algorithms.
SPAA 1990: 200-209 |
| 68 | | Mihalis Yannakakis:
The Analysis of Local Search Problems and Their Heuristics.
STACS 1990: 298-311 |
| 67 | | Christos H. Papadimitriou,
Alejandro A. Schäffer,
Mihalis Yannakakis:
On the Complexity of Local Search (Extended Abstract)
STOC 1990: 438-445 |
| 66 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On recognizing integer polyhedra.
Combinatorica 10(1): 107-109 (1990) |
| 65 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Towards an Architecture-Independent Analysis of Parallel Algorithms.
SIAM J. Comput. 19(2): 322-328 (1990) |
| 1989 |
|---|
| 64 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Shortest Paths Without a Map.
ICALP 1989: 610-620 |
| 63 | | Vijay V. Vazirani,
Mihalis Yannakakis:
Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs.
Discrete Applied Mathematics 25(1-2): 179-190 (1989) |
| 62 | | Mihalis Yannakakis:
Embedding Planar Graphs in Four Pages.
J. Comput. Syst. Sci. 38(1): 36-67 (1989) |
| 61 | | Thanasis Hadzilacos,
Mihalis Yannakakis:
Deleting Completed Transactions.
J. Comput. Syst. Sci. 38(2): 360-379 (1989) |
| 1988 |
|---|
| 60 | | Costas Courcoubetis,
Mihalis Yannakakis:
Verifying Temporal Properties of Finite-State Probabilistic Programs
FOCS 1988: 338-345 |
| 59 | | Vijay V. Vazirani,
Mihalis Yannakakis:
Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs.
ICALP 1988: 667-681 |
| 58 | | Mihalis Yannakakis:
Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract)
STOC 1988: 223-228 |
| 57 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Optimization, Approximation, and Complexity Classes (Extended Abstract)
STOC 1988: 229-234 |
| 56 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract)
STOC 1988: 510-513 |
| 55 | | David S. Johnson,
Christos H. Papadimitriou,
Mihalis Yannakakis:
On Generating All Maximal Independent Sets.
Inf. Process. Lett. 27(3): 119-123 (1988) |
| 54 | | David S. Johnson,
Christos H. Papadimitriou,
Mihalis Yannakakis:
How Easy is Local Search?
J. Comput. Syst. Sci. 37(1): 79-100 (1988) |
| 1987 |
|---|
| 53 | | Mihalis Yannakakis,
Fanica Gavril:
The Maximum k-Colorable Subgraph Problem for Chordal Graphs.
Inf. Process. Lett. 24(2): 133-137 (1987) |
| 52 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
The Complexity of Reliable Concurrency Control.
SIAM J. Comput. 16(3): 538-553 (1987) |
| 1986 |
|---|
| 51 | | Mihalis Yannakakis:
Linear and Book Embeddings of Graphs.
Aegean Workshop on Computing 1986: 226-235 |
| 50 | | Thanasis Hadzilacos,
Mihalis Yannakakis:
Deleting Completed Transactions.
PODS 1986: 43-46 |
| 49 | | Mihalis Yannakakis:
Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract)
STOC 1986: 104-108 |
| 48 | | Mihalis Yannakakis:
Querying Weak Instances.
Advances in Computing Research 3: 185-211 (1986) |
| 47 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
A Note on Succinct Representations of Graphs
Information and Control 71(3): 181-185 (1986) |
| 46 | | Ouri Wolfson,
Mihalis Yannakakis:
Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.
J. Comput. Syst. Sci. 33(2): 161-178 (1986) |
| 1985 |
|---|
| 45 | | David S. Johnson,
Christos H. Papadimitriou,
Mihalis Yannakakis:
How Easy Is Local Search? (Extended Abstract)
FOCS 1985: 39-42 |
| 44 | | Ouri Wolfson,
Mihalis Yannakakis:
Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.
PODS 1985: 105-112 |
| 43 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
The Complexity of Reliable Concurrency Control.
PODS 1985: 230-234 |
| 42 | | Mihalis Yannakakis:
A Polynomial Algorithm for the Min-Cut Linear Arrangement of Trees
J. ACM 32(4): 950-988 (1985) |
| 41 | | Robert Endre Tarjan,
Mihalis Yannakakis:
Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.
SIAM J. Comput. 14(1): 254-255 (1985) |
| 1984 |
|---|
| 40 | | Mihalis Yannakakis:
Querying Weak Instances.
PODS 1984: 275-280 |
| 39 | | Maria M. Klawe,
Wolfgang J. Paul,
Nicholas Pippenger,
Mihalis Yannakakis:
On Monotone Formulae with Restricted Depth (Preliminary Version)
STOC 1984: 480-487 |
| 38 | | Mihalis Yannakakis:
Serializability by Locking.
J. ACM 31(2): 227-244 (1984) |
| 37 | | Marc H. Graham,
Mihalis Yannakakis:
Independent Database Schemas.
J. Comput. Syst. Sci. 28(1): 121-141 (1984) |
| 36 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
The Complexity of Facets (and Some Facets of Complexity).
J. Comput. Syst. Sci. 28(2): 244-259 (1984) |
| 35 | | Robert Endre Tarjan,
Mihalis Yannakakis:
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.
SIAM J. Comput. 13(3): 566-579 (1984) |
| 1983 |
|---|
| 34 | | Mihalis Yannakakis:
A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract)
FOCS 1983: 274-281 |
| 33 | | Mihalis Yannakakis,
Paris C. Kanellakis,
Stavros S. Cosmadakis,
Christos H. Papadimitriou:
Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract).
ICALP 1983: 712-722 |
| 32 | | Alfred V. Aho,
Jeffrey D. Ullman,
Mihalis Yannakakis:
On Notions of Information Transfer in VLSI Circuits
STOC 1983: 133-139 |
| 31 | | Catriel Beeri,
Ronald Fagin,
David Maier,
Mihalis Yannakakis:
On the Desirability of Acyclic Database Schemes
J. ACM 30(3): 479-513 (1983) |
| 30 | | Ronald Fagin,
David Maier,
Jeffrey D. Ullman,
Mihalis Yannakakis:
Tools for Template Dependencies.
SIAM J. Comput. 12(1): 36-59 (1983) |
| 1982 |
|---|
| 29 | | Marc H. Graham,
Mihalis Yannakakis:
Independent Database Schemas.
PODS 1982: 199-204 |
| 28 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
The Complexity of Facets (and Some Facets of Complexity)
STOC 1982: 255-260 |
| 27 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
The complexity of restricted spanning tree problems.
J. ACM 29(2): 285-309 (1982) |
| 26 | | Mihalis Yannakakis:
A Theory of Safe Locking Policies in Database Systems.
J. ACM 29(3): 718-740 (1982) |
| 25 | | Mihalis Yannakakis,
Christos H. Papadimitriou:
Algebraic Dependencies.
J. Comput. Syst. Sci. 25(1): 2-41 (1982) |
| 24 | | Mihalis Yannakakis:
Freedom from Deadlock of Safe Locking Policies.
SIAM J. Comput. 11(2): 391-408 (1982) |
| 1981 |
|---|
| 23 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract)
FOCS 1981: 358-363 |
| 22 | | Catriel Beeri,
Ronald Fagin,
David Maier,
Alberto O. Mendelzon,
Jeffrey D. Ullman,
Mihalis Yannakakis:
Properties of Acyclic Database Schemes
STOC 1981: 355-362 |
| 21 | | Mihalis Yannakakis:
Issues of Correctness in Database Concurrency Control by Locking
STOC 1981: 363-367 |
| 20 | | Mihalis Yannakakis:
Algorithms for Acyclic Database Schemes
VLDB 1981: 82-94 |
| 19 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
On Minimal Eulerian Graphs.
Inf. Process. Lett. 12(4): 203-205 (1981) |
| 18 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
The Clique Problem for Planar Graphs.
Inf. Process. Lett. 13(4/5): 131-133 (1981) |
| 17 | | Manuel Blum,
Richard M. Karp,
Oliver Vornberger,
Christos H. Papadimitriou,
Mihalis Yannakakis:
The Complexity of Testing Whether a Graph is a Superconcentrator.
Inf. Process. Lett. 13(4/5): 164-167 (1981) |
| 16 | | David Maier,
Yehoshua Sagiv,
Mihalis Yannakakis:
On the Complexity of Testing Implications of Functional and Join Dependencies.
J. ACM 28(4): 680-695 (1981) |
| 15 | | Mihalis Yannakakis:
Edge-Deletion Problems.
SIAM J. Comput. 10(2): 297-309 (1981) |
| 14 | | Mihalis Yannakakis:
Node-Deletion Problems on Bipartite Graphs.
SIAM J. Comput. 10(2): 310-327 (1981) |
| 1980 |
|---|
| 13 | | Mihalis Yannakakis:
On a Class of Totally Unimodular Matrices
FOCS 1980: 10-16 |
| 12 | | Mihalis Yannakakis,
Christos H. Papadimitriou:
Algebraic Dependencies (Extended Abstract)
FOCS 1980: 328-332 |
| 11 | | Peter Honeyman,
Richard E. Ladner,
Mihalis Yannakakis:
Testing the Universal Instance Assumption.
Inf. Process. Lett. 10(1): 14-19 (1980) |
| 10 | | Yehoshua Sagiv,
Mihalis Yannakakis:
Equivalences Among Relational Expressions with the Union and Difference Operators.
J. ACM 27(4): 633-655 (1980) |
| 9 | | John M. Lewis,
Mihalis Yannakakis:
The Node-Deletion Problem for Hereditary Properties is NP-Complete.
J. Comput. Syst. Sci. 20(2): 219-230 (1980) |
| 1979 |
|---|
| 8 | | Alfred V. Aho,
Jeffrey D. Ullman,
Mihalis Yannakakis:
Modeling Communications Protocols by Automata
FOCS 1979: 267-273 |
| 7 | | Mihalis Yannakakis,
Christos H. Papadimitriou,
H. T. Kung:
Locking Policies: Safety and Freedom from Deadlock
FOCS 1979: 286-297 |
| 6 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract).
ICALP 1979: 460-470 |
| 5 | | Mihalis Yannakakis,
Theodosios Pavlidis:
Topological Characterization of Families of Graphs Generated by Certain Types of Graph Grammars
Information and Control 42(1): 72-86 (1979) |
| 4 | | Mihalis Yannakakis:
The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems.
J. ACM 26(4): 618-630 (1979) |
| 3 | | Christos H. Papadimitriou,
Mihalis Yannakakis:
Scheduling Interval-Ordered Tasks.
SIAM J. Comput. 8(3): 405-409 (1979) |
| 1978 |
|---|
| 2 | | Mihalis Yannakakis:
Node- and Edge-Deletion NP-Complete Problems
STOC 1978: 253-264 |
| 1 | | Yehoshua Sagiv,
Mihalis Yannakakis:
Equivalence among Relational Expressions with the Union and Difference Operation.
VLDB 1978: 535-548 |
