BibSLEIGH — Mihalis

Travelled to:

1 × Iceland
1 × Ireland
1 × Israel
1 × Japan
1 × Latvia
1 × Russia
1 × Spain
1 × Sweden
2 × Austria
2 × Czech Republic
2 × Denmark
2 × Germany
2 × Greece
2 × Portugal
2 × United Kingdom
26 × USA
3 × Finland
3 × France
3 × Italy
4 × Canada

Collaborated with:

C.H.Papadimitriou ∅ K.Etessami R.Alur D.Lee V.V.Vazirani A.Stewart C.Courcoubetis N.Garg C.Lund J.D.Ullman A.Groce D.Peled R.P.Kurshan S.S.Cosmadakis P.Godefroid M.Y.Vardi S.Vassilvitskii T.Hadzilacos O.Wolfson M.H.Graham Y.Sagiv X.Chen D.Paparas D.Wojtczak S.Kannan O.Kupferman E.Koutsoupias F.N.Afrati A.A.Schäffer A.V.Aho D.S.Johnson M.Z.Kwiatkowska A.Itai P.Wolper M.M.Klawe W.J.Paul N.Pippenger P.C.Kanellakis V.Guruswami S.Khanna R.Rajaraman F.B.Shepherd P.Crescenzi D.Goldman A.Piccolboni E.Dahlhaus P.D.Seymour A.Blum T.Jiang M.Li J.Tromp C.Beeri R.Fagin D.Maier A.O.Mendelzon E.G.C.Jr. M.R.Garey L.A.McGeoch P.W.Shor R.R.Weber

Talks about:

complex (12) algorithm (9) approxim (8) databas (7) recurs (7) graph (7) polynomi (6) process (6) problem (6) machin (6)

Person: Mihalis Yannakakis

DBLP: Yannakakis:Mihalis

Facilitated 3 volumes:

Contributed to:

2015

2013

2012

2008

2007

2006

2005

2004

2002

2001

2000

1999

1998

1997

1996

1995

1994

1993

1992

1991

1990

1989

1988

1986

1985

1984

1983

1982

1981

1979

1978

Wrote 74 papers:

ICALP-v2-2015-EtessamiSY #branch #equation #fixpoint #markov #polynomial #probability #process #reachability: Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes (KE, AS, MY), pp. 184–196.
CAV-2013-StewartEY #automaton #bound #model checking #polynomial #probability: Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata (AS, KE, MY), pp. 495–510.
ICALP-v2-2013-EtessamiSY #context-free grammar #probability #regular expression: Stochastic Context-Free Grammars, Regular Languages, and Newton’s Method (KE, AS, MY), pp. 199–211.
STOC-2013-ChenPY #complexity: The complexity of non-monotone markets (XC, DP, MY), pp. 181–190.
TACAS-2013-GodefroidY #analysis #source code: Analysis of Boolean Programs (PG, MY), pp. 214–229.
ICALP-v1-2012-EtessamiSY #algorithm #branch #equation #markov #polynomial #probability #process: Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations (KE, AS, MY), pp. 314–326.
STOC-2012-EtessamiSY #algorithm #branch #context-free grammar #multi #polynomial #probability #process: Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars (KE, AS, MY), pp. 579–588.
CIAA-2008-Yannakakis #automaton #probability #recursion: Automata, Probability, and Recursion (MY), pp. 23–32.
ICALP-A-2008-EtessamiWY #game studies #probability #recursion: Recursive Stochastic Games with Positive Rewards (KE, DW, MY), pp. 711–723.
TACAS-2007-EtessamiKVY #markov #model checking #multi #process: Multi-objective Model Checking of Markov Decision Processes (KE, MZK, MYV, MY), pp. 50–65.
ICALP-v2-2006-EtessamiY #concurrent #game studies #probability #recursion: Recursive Concurrent Stochastic Games (KE, MY), pp. 324–335.
ICALP-2005-EtessamiY #game studies #markov #probability #process #recursion: Recursive Markov Decision Processes and Recursive Stochastic Games (KE, MY), pp. 891–903.
TACAS-2005-EtessamiY #algorithm #probability #recursion #state machine #verification: Algorithmic Verification of Recursive Probabilistic State Machines (KE, MY), pp. 253–270.
ICALP-2004-VassilvitskiiY #trade-off: Efficiently Computing Succinct Trade-Off Curves (SV, MY), pp. 1201–1213.
ICALP-2004-Yannakakis #game studies #testing: Testing, Optimizaton, and Games (MY), pp. 28–45.
LICS-2004-Yannakakis #game studies #testing: Testing, Optimizaton, and Games (MY), pp. 78–88.
CAV-2002-GrocePY #adaptation #model checking #named: AMC: An Adaptive Model Checker (AG, DP, MY), pp. 521–525.
TACAS-2002-GrocePY #adaptation #model checking: Adaptive Model Checking (AG, DP, MY), pp. 357–370.
CAV-2001-AlurEY #analysis #recursion #state machine: Analysis of Recursive State Machines (RA, KE, MY), pp. 207–220.
ICALP-2001-AlurEY #graph #verification: Realizability and Verification of MSC Graphs (RA, KE, MY), pp. 797–808.
PODS-2001-PapadimitriouY #multi #optimisation #query: Multiobjective Query Optimization (CHP, MY).
ICSE-2000-AlurEY #sequence chart: Inference of message sequence charts (RA, KE, MY), pp. 304–313.
ICALP-1999-AlurKY #communication #state machine: Communicating Hierarchical State Machines (RA, SK, MY), pp. 169–178.
STOC-1999-GuruswamiKRSY #algorithm #approximate #problem: Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems (VG, SK, RR, FBS, MY), pp. 19–28.
CSL-1998-YannakakisL #finite #testing: Testing for Finite State Systems (MY, DL), pp. 29–44.
FSE-1998-AlurY #model checking #state machine: Model Checking of Hierarchical State Machines (RA, MY), pp. 175–188.
STOC-1998-CrescenziGPPY #complexity #on the: On the Complexity of Protein Folding (PC, DG, CHP, AP, MY), pp. 597–603.
CSL-1997-KupfermanKY #reduction: Existence of Reduction Hierarchies (OK, RPK, MY), pp. 327–340.
PODS-1997-PapadimitriouY #complexity #database #on the #query: On the Complexity of Database Queries (CHP, MY), pp. 12–19.
ICALP-1996-KoutsoupiasPY #graph: Searching a Fixed Graph (EK, CHP, MY), pp. 280–289.
STOC-1995-AlurCY #nondeterminism #probability #testing: Distinguishing tests for nondeterministic and probabilistic machines (RA, CC, MY), pp. 363–372.
ICALP-1994-GargVY #graph #multi: Multiway Cuts in Directed and Node Weighted Graphs (NG, VVV, MY), pp. 487–498.
STOC-1994-PapadimitriouY #bound #complexity #on the: On complexity as bounded rationality (CHP, MY), pp. 726–733.
CAV-1993-YannakakisL #algorithm #performance #realtime: An Efficient Algorithm for Minimizing Real-time Transition Systems (MY, DL), pp. 210–224.
ICALP-1993-GargVY #algorithm #approximate #multi #set: Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover (NG, VVV, MY), pp. 64–75.
ICALP-1993-LundY #approximate #problem: The Approximation of Maximum Subgraph Problems (CL, MY), pp. 40–51.
STOC-1993-GargVY #approximate #multi #theorem: Approximate max-flow min-(multi)cut theorems and their applications (NG, VVV, MY), pp. 698–707.
STOC-1993-LundY #approximate #on the #problem: On the hardness of approximating minimization problems (CL, MY), pp. 286–293.
STOC-1993-PapadimitriouY #linear #matrix #programming: Linear programming without the matrix (CHP, MY), pp. 121–129.
CAV-1992-AlurIKY #approximate #verification: Timing Verification by Successive Approximation (RA, AI, RPK, MY), pp. 137–150.
ICALP-1992-VaziraniY: Suboptimal Cuts: Their Enumeration, Weight and Number (VVV, MY), pp. 366–377.
PODS-1992-PapadimitriouY #semantics: Tie-Breaking Semantics and Structural Totality (CHP, MY), pp. 16–22.
STOC-1992-DahlhausJPSY #complexity #multi: The Complexity of Multiway Cuts (ED, DSJ, CHP, PDS, MY), pp. 241–251.
STOC-1992-LeeY #online: Online Minimization of Transition Systems (DL, MY), pp. 264–274.
PODS-1991-AfratiCY #datalog #on the #polynomial: On Datalog vs. Polynomial Time (FNA, SSC, MY), pp. 13–25.
STOC-1991-BlumJLTY #approximate #linear #string: Linear Approximation of Shortest Superstrings (AB, TJ, ML, JT, MY), pp. 328–336.
STOC-1991-CoffmanCGJMSWY #analysis #case study: Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study (EGCJ, CC, MRG, DSJ, LAM, PWS, RRW, MY), pp. 230–240.
STOC-1991-YannakakisL #finite #state machine #testing: Testing Finite State Machines (MY, DL), pp. 476–485.
CAV-1990-CourcoubetisVWY #algorithm #memory management #performance #verification: Memory Efficient Algorithms for the Verification of Temporal Properties (CC, MYV, PW, MY), pp. 233–242.
ICALP-1990-CourcoubetisY #markov #process: Markov Decision Processes and Regular Events (CC, MY), pp. 336–349.
PODS-1990-Yannakakis #database #graph: Graph-Theoretic Methods in Database Theory (MY), pp. 230–242.
SIGMOD-1990-UllmanY #complexity #transitive: The Input/Output Complexity of Transitive Closure (JDU, MY), pp. 44–53.
STOC-1990-PapadimitriouSY #complexity #on the: On the Complexity of Local Search (CHP, AAS, MY), pp. 438–445.
ICALP-1989-PapadimitriouY: Shortest Paths Without a Map (CHP, MY), pp. 610–620.
ICALP-1988-VaziraniY #graph: Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs (VVV, MY), pp. 667–681.
STOC-1988-PapadimitriouY88a #approximate #complexity #optimisation: Optimization, Approximation, and Complexity Classes (CHP, MY), pp. 229–234.
STOC-1988-PapadimitriouY88b #algorithm #analysis #architecture #independence #parallel #towards: Towards an Architecture-Independent Analysis of Parallel Algorithms (CHP, MY), pp. 510–513.
STOC-1988-Yannakakis #combinator #linear #optimisation #problem #source code: Expressing Combinatorial Optimization Problems by Linear Programs (MY), pp. 223–228.
PODS-1986-Hadzilacos #transaction: Deleting Completed Transactions (TH, MY), pp. 43–46.
STOC-1986-Yannakakis #graph: Four Pages are Necessary and Sufficient for Planar Graphs (MY), pp. 104–108.
PODS-1985-PapadimitriouY #complexity #concurrent #reliability: The Complexity of Reliable Concurrency Control (CHP, MY), pp. 230–234.
PODS-1985-WolfsonY #database #distributed #safety #transaction: Deadlock-Freedom (and Safety) of Transactions in a Distributed Database (OW, MY), pp. 105–112.
PODS-1984-Yannakakis #query: Querying Weak Instances (MY), pp. 275–280.
STOC-1984-KlawePPY #on the #strict: On Monotone Formulae with Restricted Depth (MMK, WJP, NP, MY), pp. 480–487.
ICALP-1983-YannakakisKCP #clustering #graph: Cutting and Partitioning a Graph aifter a Fixed Pattern (MY, PCK, SSC, CHP), pp. 712–722.
STOC-1983-AhoUY #on the: On Notions of Information Transfer in VLSI Circuits (AVA, JDU, MY), pp. 133–139.
PODS-1982-GrahamY #database #independence: Independent Database Schemas (MHG, MY), pp. 199–204.
STOC-1982-PapadimitriouY #complexity: The Complexity of Facets (and Some Facets of Complexity) (CHP, MY), pp. 255–260.
STOC-1981-BeeriFMMUY #database: Properties of Acyclic Database Schemes (CB, RF, DM, AOM, JDU, MY), pp. 355–362.
STOC-1981-Yannakakis #concurrent #correctness #database: Issues of Correctness in Database Concurrency Control by Locking (MY), pp. 363–367.
VLDB-1981-Yannakakis #algorithm #database: Algorithms for Acyclic Database Schemes (MY), pp. 82–94.
ICALP-1979-PapadimitriouY #complexity #problem #strict: The Complexity of Restricted Minimum Spanning Tree Problems (CHP, MY), pp. 460–470.
STOC-1978-Yannakakis #problem: Node- and Edge-Deletion NP-Complete Problems (MY), pp. 253–264.
VLDB-1978-SagivY #difference #equivalence #relational: Equivalence among Relational Expressions with the Union and Difference Operation (YS, MY), pp. 535–548.