Dynamic phase transition for decoding algorithms.
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.
Franz
S
S
International Center for Theoretical Physics, P.O. Box 586, I-34100 Trieste, Italy. franz@ictp.trieste.it
Leone
Michele
M
Montanari
Andrea
A
Ricci-Tersenghi
Federico
F