BibSLEIGH
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
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 DBLP: Yannakakis:Mihalis

Facilitated 3 volumes:

STOC 2001Ed
PODS 1995Ed
PODS 1988Ed

Contributed to:

ICALP (2) 20152015
CAV 20132013
ICALP (2) 20132013
STOC 20132013
TACAS 20132013
ICALP (1) 20122012
STOC 20122012
CIAA 20082008
ICALP (1) 20082008
TACAS 20072007
ICALP (2) 20062006
ICALP 20052005
TACAS 20052005
ICALP 20042004
LICS 20042004
CAV 20022002
TACAS 20022002
CAV 20012001
ICALP 20012001
PODS 20012001
ICSE 20002000
ICALP 19991999
STOC 19991999
CSL 19981998
FSE 19981998
STOC 19981998
CSL 19971997
PODS 19971997
ICALP 19961996
STOC 19951995
ICALP 19941994
STOC 19941994
CAV 19931993
ICALP 19931993
STOC 19931993
CAV 19921992
ICALP 19921992
PODS 19921992
STOC 19921992
PODS 19911991
STOC 19911991
CAV 19901990
ICALP 19901990
PODS 19901990
SIGMOD 19901990
STOC 19901990
ICALP 19891989
ICALP 19881988
STOC 19881988
PODS 19861986
STOC 19861986
PODS 19851985
PODS 19841984
STOC 19841984
ICALP 19831983
STOC 19831983
PODS 19821982
STOC 19821982
STOC 19811981
VLDB 19811981
ICALP 19791979
STOC 19781978
VLDB 19781978

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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.