Pacific Institute for the Mathematical Sciences - PIMS

Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of
Computer Science at Columbia University. Prior to joining Columbia, he
was Director of the Computing Principles Research Department at Bell
Labs (1991-2001) and at Avaya Labs (2001-2002), and Professor of
Computer Science at Stanford University (2002-2003). Dr. Yannakakis
received his PhD from Princeton University in 1979. His research
interests include algorithms, complexity, optimization, databases,
testing and verification. He has served on the editorial boards of
several journals, including as the past editor-in-chief of the SIAM
Journal on Computing, and has chaired various conferences, including
the IEEE Symposium on Foundations of Computer Science, the ACM
Symposium on Theory of Computing and the ACM Symposium on Principles of
Database Systems. Dr. Yannakakis is a Fellow of the ACM and of Bell
Labs, and a recipient of the Knuth Prize.
Abstract: We discuss recent work on the modeling and algorithmic
analysis of systems involving recursion and probability. Recursive
Markov chains extend ordinary finite state Markov chains with the
ability to invoke other Markov chains in a potentially recursive
manner. They offer a natural abstract model of probabilistic programs
with procedures, and generalize other classical well-studied stochastic
models, eg. Branching Processes and Stochastic Context-free Grammars,
that have been used in a variety of areas. Recursive Markov Decision
Processes and Stochastic Games similarly extend ordinary finite
decision processes and games, and they are natural models for recursive
systems involving both probabilistic and nonprobabilistic (controlled)
actions. In a series of recent papers with Kousha Etessami (U. of
Edinburgh), we have introduced these models and studied central
algorithmic problems regarding questions of termination, reachability,
and analysis of the properties of their executions. In this talk we
will present some of the basic theory and algorithms.

PIMS/SFU Computing Science DISTINGUISHED LECTURE SERIES 2007