Mihalis Yannakakis Papers on DiSC'02 Multiobjective Query Optimization Publications Note: Links lead to the DBLP on the Web. Mihalis Yannakakis 147 Mihalis Yannakakis: Testing and Checking of Finite State Systems. LATIN 2002 : 14 146 Alex Groce , Doron Peled , Mihalis Yannakakis: Adaptive Model Checking. TACAS 2002 : 357-370 145 David Lee , Mihalis Yannakakis: Closed Partition Lattice and Machine Decomposition. IEEE Transactions on Computers 51 (2): 216-228 (2002) 144 Rajeev Alur , Kousha Etessami , Mihalis Yannakakis: Analysis of Recursive State Machines. CAV 2001 : 207-220 143 Rajeev Alur , Kousha Etessami , Mihalis Yannakakis: Realizability and Verification of MSC Graphs. ICALP 2001 : 797-808 142 Christos H. Papadimitriou , Mihalis Yannakakis: Multiobjective Query Optimization. PODS 2001 141 Mihalis Yannakakis: Approximation of Multiobjective Optimization Problems. WADS 2001 : 1 140 Rajeev Alur , Mihalis Yannakakis: Model checking of hierarchical state machines. TOPLAS 23 (3): 273-303 (2001) 139 Christos H. Papadimitriou , Mihalis Yannakakis: On the Approximability of Trade-offs and Optimal Access of Web Sources. FOCS 2000 : 86-92 138 Kousha Etessami , Mihalis Yannakakis: From Rule-based to Automata-based Testing. FORTE 2000 : 53-68 137 Rajeev Alur , Kousha Etessami , Mihalis Yannakakis: Inference of message sequence charts. ICSE 2000 : 304-313 136 Mihalis Yannakakis: Hierarchical State Machines. IFIP TCS 2000 : 315-330 135 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 Journal on Discrete Mathematics 13 (3): 384-402 (2000) 134 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) 133 Rajeev Alur , Mihalis Yannakakis: Model Checking of Message Sequence Charts. CONCUR 1999 : 114-129 132 Doron Peled , Moshe Y. Vardi , Mihalis Yannakakis: Black Box Checking. FORTE 1999 : 225-240 131 Rajeev Alur , Sampath Kannan , Mihalis Yannakakis: Communicating Hierarchical State Machines. ICALP 1999 : 169-178 130 Santosh Vempala , Mihalis Yannakakis: A Convex Relaxation for the Asymmetric TSP. SODA 1999 : 975-976 129 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 128 Christos H. Papadimitriou , Mihalis Yannakakis: On the Complexity of Database Queries. JCSS 58 (3): 407-427 (1999) 127 Mihalis Yannakakis, David Lee : Testing for Finite State Systems. CSL 1998 : 29-44 126 Thomas F. La Porta , David Lee , Yow-Jian Lin , Mihalis Yannakakis: Protocol Feature Interactions. FORTE 1998 : 59-74 125 Pierluigi Crescenzi , Deborah Goldman , Christos H. Papadimitriou , Antonio Piccolboni , Mihalis Yannakakis: On the complexity of protein folding (abstract). RECOMB 1998 : 61-62 124 Rajeev Alur , Mihalis Yannakakis: Model Checking of Hierarchical State Machines. SIGSOFT FSE 1998 : 175-188 123 Pierluigi Crescenzi , Deborah Goldman , Christos H. Papadimitriou , Antonio Piccolboni , Mihalis Yannakakis: On the Complexity of Protein Folding (Extended Abstract). STOC 1998 : 597-603 122 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) 121 Orna Kupferman , Robert P. Kurshan , Mihalis Yannakakis: Existence of Reduction Hierarchies. CSL 1997 : 327-340 120 Christos H. Papadimitriou , Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997 : 12-19 119 Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis: Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica 18 (1): 3-20 (1997) 118 Mihalis Yannakakis, David Lee : An Efficient Algorithm for Minimizing Real-Time Transition Systems. Formal Methods in System Design 11 (2): 113-136 (1997) 117 Christos H. Papadimitriou , Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. JCSS 54 (1): 48-60 (1997) 116 Elias Koutsoupias , Christos H. Papadimitriou , Mihalis Yannakakis: Searching a Fixed Graph. ICALP 1996 : 280-289 115 Christos H. Papadimitriou , Mihalis Yannakakis: On Limited Nondeterminism and the Complexity of the V-C Dimension. JCSS 53 (2): 161-170 (1996) 114 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) 113 Mihalis Yannakakis: Perspectives on Database Theory. FOCS 1995 : 224-246 112 Rajeev Alur , Costas Courcoubetis , Mihalis Yannakakis: Distinguishing tests for nondeterministic and probabilistic machines. STOC 1995 : 363-372 111 Rajeev Alur , Alon Itai , Robert P. Kurshan , Mihalis Yannakakis: Timing Verification by Successive Approximation. Information and Computation 118 (1): 142-157 (1995) 110 Costas Courcoubetis , Mihalis Yannakakis: The Complexity of Probabilistic Verification. JACM 42 (4): 857-907 (1995) 109 Mihalis Yannakakis, David Lee : Testing Finite State Machines: Fault Detection. JCSS 50 (2): 209-227 (1995) 108 Foto N. Afrati , Stavros S. Cosmadakis , Mihalis Yannakakis: On Datalog vs. Polynomial Time. JCSS 51 (2): 177-196 (1995) 107 Mihalis Yannakakis: Some Open Problems in Approximation. CIAC 1994 : 33-39 106 Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis: Multiway Cuts in Directed and Node Weighted Graphs. ICALP 1994 : 487-498 105 Christos H. Papadimitriou , Mihalis Yannakakis: On Complexity as Bounded Rationality (Extended Abstract). STOC 1994 : 726-733 104 David Lee , Mihalis Yannakakis: Testing Finite-State Machines: State Identification and Verification. IEEE Transactions on Computers 43 (3): 306-320 (1994) 103 Mihalis Yannakakis: On the Approximation of Maximum Satisfiability. J. Algorithms 17 (3): 475-502 (1994) 102 Avrim Blum , Ming Li , John Tromp , Mihalis Yannakakis: Linear Approximation of Shortest Superstrings. JACM 41 (4): 630-647 (1994) 101 Carsten Lund , Mihalis Yannakakis: On the Hardness of Approximating Minimization Problems. JACM 41 (5): 960-981 (1994) 100 Elias Dahlhaus , David S. Johnson , Christos H. Papadimitriou , P. D. Seymour , Mihalis Yannakakis: The Complexity of Multiterminal Cuts. SIAM J. Comput. 23 (4): 864-894 (1994) 99 Mihalis Yannakakis, David Lee : An Efficient Algorithm for Minimizing Real-time Transition Systems. CAV 1993 : 210-224 98 Carsten Lund , Mihalis Yannakakis: The Approximation of Maximum Subgraph Problems. ICALP 1993 : 40-51 97 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 96 Mihalis Yannakakis: Recent Developments on the Approximability of Combinatorial Problems. ISAAC 1993 : 363-368 95 Christos H. Papadimitriou , Mihalis Yannakakis: Linear Programming without the Matrix (Extended Abstract). STOC 1993 : 121-129 94 Carsten Lund , Mihalis Yannakakis: On the Hardness of Approximating Minimization Problems (Extended Abstract). STOC 1993 : 286-293 93 Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis: Approximate Max-flow Min-(multi)cut Theorems and Their Applications. STOC 1993 : 698-707 92 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 91 Christos H. Papadimitriou , Paolo Serafini , Mihalis Yannakakis: Computing the Throughput of a Network with Dedicated Lines. Discrete Applied Mathematics 42 (2): 271-278 (1993) 90 Rajeev Alur , Alon Itai , Robert P. Kurshan , Mihalis Yannakakis: Timing Verification by Successive Approximation. CAV 1992 : 137-150 89 Vijay V. Vazirani , Mihalis Yannakakis: Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract). ICALP 1992 : 366-377 88 Christos H. Papadimitriou , Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. PODS 1992 : 16-22 87 Mihalis Yannakakis: On the Approximation of Maximum Satisfiability. SODA 1992 : 1-9 86 Elias Dahlhaus , David S. Johnson , Christos H. Papadimitriou , P. D. Seymour , Mihalis Yannakakis: The Complexity of Multiway Cuts (Extended Abstract). STOC 1992 : 241-251 85 David Lee , Mihalis Yannakakis: Online Minimization of Transition Systems (Extended Abstract). STOC 1992 : 264-274 84 Constantin 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) 83 Costas Courcoubetis , Mihalis Yannakakis: Minimum and Maximum Delay Problems in Real-Time Systems. Formal Methods in System Design 1 (4): 385-415 (1992) 82 Christos H. Papadimitriou , Mihalis Yannakakis: On the Value of Information in Distributed Decision-Making (Extended Abstract). PODC 1991 : 61-64 81 Foto N. Afrati , Stavros S. Cosmadakis , Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991 : 13-25 80 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 79 Avrim Blum , Tao Jiang , Ming Li , John Tromp , Mihalis Yannakakis: Linear Approximation of Shortest Superstrings. STOC 1991 : 328-336 78 Mihalis Yannakakis, David Lee : Testing Finite State Machines (Extended Abstract). STOC 1991 : 476-485 77 Jeffrey D. Ullman , Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. Annals of Mathematics and Artificial Intelligence 3 (2-4): 331-360 (1991) 76 Esther M. Arkin , Christos H. Papadimitriou , Mihalis Yannakakis: Modularity of Cycles and Paths in Graphs. JACM 38 (2): 255-274 (1991) 75 Christos H. Papadimitriou , Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes. JCSS 43 (3): 425-440 (1991) 74 Mihalis Yannakakis: Expressing Combinatorial Optimization Problems by Linear Programs. JCSS 43 (3): 441-466 (1991) 73 Jeffrey D. Ullman , Mihalis Yannakakis: High-Probability Parallel Transitive-Closure Algorithms. SIAM J. Comput. 20 (1): 100-125 (1991) 72 Alejandro A. Schäffer , Mihalis Yannakakis: Simple Local Search Problems That are Hard to Solve. SIAM J. Comput. 20 (1): 56-87 (1991) 71 Christos H. Papadimitriou , Mihalis Yannakakis: Shortest Paths Without a Map. TCS 84 (1): 127-150 (1991) 70 Costas Courcoubetis , Moshe Y. Vardi , Pierre Wolper , Mihalis Yannakakis: Memory Efficient Algorithms for the Verification of Temporal Properties. CAV 1990 : 233-242 69 Costas Courcoubetis , Mihalis Yannakakis: Markov Decision Processes and Regular Events (Extended Abstract). ICALP 1990 : 336-349 68 Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990 : 230-242 67 Jeffrey D. Ullman , Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. SIGMOD Conference 1990 : 44-53 66 Jeffrey D. Ullman , Mihalis Yannakakis: High-Probability Parallel Transitive Closure Algorithms. SPAA 1990 : 200-209 65 Mihalis Yannakakis: The Analysis of Local Search Problems and Their Heuristics. STACS 1990 : 298-311 64 Christos H. Papadimitriou , Alejandro A. Schäffer , Mihalis Yannakakis: On the Complexity of Local Search (Extended Abstract). STOC 1990 : 438-445 63 Christos H. Papadimitriou , Mihalis Yannakakis: Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput. 19 (2): 322-328 (1990) 62 Christos H. Papadimitriou , Mihalis Yannakakis: Shortest Paths Without a Map. ICALP 1989 : 610-620 61 Mihalis Yannakakis: Embedding Planar Graphs in Four Pages. JCSS 38 (1): 36-67 (1989) 60 Thanasis Hadzilacos , Mihalis Yannakakis: Deleting Completed Transactions. JCSS 38 (2): 360-379 (1989) 59 Costas Courcoubetis , Mihalis Yannakakis: Verifying Temporal Properties of Finite-State Probabilistic Programs. FOCS 1988 : 338-345 58 Vijay V. Vazirani , Mihalis Yannakakis: Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs. ICALP 1988 : 667-681 57 Mihalis Yannakakis: Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract). STOC 1988 : 223-228 56 Christos H. Papadimitriou , Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes (Extended Abstract). STOC 1988 : 229-234 55 Christos H. Papadimitriou , Mihalis Yannakakis: Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract). STOC 1988 : 510-513 54 David S. Johnson , Christos H. Papadimitriou , Mihalis Yannakakis: How Easy is Local Search? JCSS 37 (1): 79-100 (1988) 53 Mihalis Yannakakis, Fanica Gavril : The Maximum k-Colorable Subgraph Problem for Chordal Graphs. Information Processing Letters 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) 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. JCSS 33 (2): 161-178 (1986) 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. JACM 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) 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. JACM 31 (2): 227-244 (1984) 37 Marc H. Graham , Mihalis Yannakakis: Independent Database Schemas. JCSS 28 (1): 121-141 (1984) 36 Christos H. Papadimitriou , Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). JCSS 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) 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. JACM 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) 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. JACM 29 (2): 285-309 (1982) 26 Mihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. JACM 29 (3): 718-740 (1982) 25 Mihalis Yannakakis, Christos H. Papadimitriou : Algebraic Dependencies. JCSS 25 (1): 2-41 (1982) 24 Mihalis Yannakakis: Freedom from Deadlock of Safe Locking Policies. SIAM J. Comput. 11 (2): 391-408 (1982) 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. Information Processing Letters 12 (4): 203-205 (1981) 18 Christos H. Papadimitriou , Mihalis Yannakakis: The Clique Problem for Planar Graphs. Information Processing Letters 13 (3): 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. Information Processing Letters 13 (3): 164-167 (1981) 16 David Maier , Yehoshua Sagiv , Mihalis Yannakakis: On the Complexity of Testing Implications of Functional and Join Dependencies. JACM 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) 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. Information Processing Letters 10 (1): 14-19 (1980) 10 Yehoshua Sagiv , Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. JACM 27 (4): 633-655 (1980) 9 John M. Lewis , Mihalis Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. JCSS 20 (2): 219-230 (1980) 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. JACM 26 (4): 618-630 (1979) 3 Christos H. Papadimitriou , Mihalis Yannakakis: Scheduling Interval-Ordered Tasks. SIAM J. Comput. 8 (3): 405-409 (1979) 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 DiSC'02 © 2003 Association for Computing Machinery