Dynamical transitions in graphical models and decodability

Ensembles of statistical models appear naturally in the physics of disordered materials, error correcting codes, and the analysis of algorithms for optimization problems. In many generic ensembles there are believed to be two transitions at high temperature: a "dynamical" transition, followed by a lower temperature "replica symmetry breaking" transition. A large family of graphical models are dual (for certain quantities) to a decoding problem on a related error correcting code. We exploit this duality to give analytical computations of the dynamical (and replica symmetry breaking) transition point for certain cases. Based on the properties of these examples near the dynamical transition, we discuss some conjectures connecting the dynamical transition, optimization algorithms, and cooling dynamics.