  In this paper we study the problem of learning phylogenies and hidden Markov
models. We call a Markov model nonsingular if all transition matrices have
determinants bounded away from 0 (and 1). We highlight the role of the
nonsingularity condition for the learning problem. Learning hidden Markov
models without the nonsingularity condition is at least as hard as learning
parity with noise, a well-known learning problem conjectured to be
computationally hard. On the other hand, we give a polynomial-time algorithm
for learning nonsingular phylogenies and hidden Markov models.
