Dynamic Graphical models (including hidden Markov models, Dynamic
Bayesian networks, and temporal conditional random fields) are a
general statistical abstraction for time series that are widely used
in speech recognition, language processing, bio-informatics, and other
time-series applications.  Such time series, however, have properties
that introduce unique research problems.  The first part of this talk
will present a variety of graph structures that solve many problems in
these areas.  Next, we will outline the computational challenges in
applying this framework on very large problems.  We will describe
novel exact and approximate inference procedures for computing with
these models which involves, perhaps as expected, graph triangulation,
conditioning, and search procedures, but perhaps more surprisingly,
also involves optimal bin packing, max-flow procedures, and other
graph cut problems.