This talk will consist of two distinct but linked parts. Firstly I will
review some key notions from statistical physics, such as 'phase
transitions' and their connection to a variety of questions in
computational complexity and the analysis of randomized algorithms. In
the second part I will introduce a class of Monte Carlo Markov Chains
which exihibit the phenomenon of "dynamical arrest", namely a dramatic
increase of their mixing time when some parameter goes beyond a given
threshold, without any counterpart at the level of their invariant
measure. Besides their relevance to the description of glassy systems,
some of these models may be of interest also to the theoretical computer
science community.