title: Dynamic phase transition for decoding algorithms.
abstract: The state-of-the-art error correcting codes are based on large random constructions (random graphs, random permutations, etc.) and are decoded by linear-time iterative algorithms. Because of these features, they are remarkable examples of diluted mean-field spin glasses, both from the static and dynamic points of view. We analyze the behavior of decoding algorithms by mapping them onto statistical-physics models. This allows us to understand the intrinsic (i.e., algorithm independent) features of this behavior.
authors.affiliation: International Center for Theoretical Physics, P.O. Box 586, I-34100 Trieste, Italy. franz@ictp.trieste.it
authors.forename: S
authors.initials: S
authors.lastname: Franz
authors.forename: Michele
authors.initials: M
authors.lastname: Leone
authors.forename: Andrea
authors.initials: A
authors.lastname: Montanari
authors.forename: Federico
authors.initials: F
authors.lastname: Ricci-Tersenghi