2009 Discrete Maths Seminar - 04

  • Date: 02/24/2009
Lecturer(s):
Alexander Schönhuth (PIMS/SFU)
Location: 

University of British Columbia

Topic: 

A simple and efficient solution of the identifiability problem for hidden Markov sources and quantum random walks

Description: 

A solution of the identifiability problem (IP) for hidden Markov models
(HMMs), based on a novel algebraic theory for random sources, is
presented. It gives rise to an efficient and practical algorithm that
can be easily implemented. Extant approaches are exponential in the
number of hidden states and therefore only applicable to a limited
degree. The algorithm can be equally applied to solve the IP for
quantum random walks (QRWs) that have recently been presented as an
analogon of Markov chains in quantum information theory. Moreover, the
algorithm can be used to efficiently test HMMs and QRWs for ergodicity,
which had remained an open problem so far.

Schedule: 

4:00pm-5:00pm, WMAX 216

Sponsor: 

pims