TY - GEN

T1 - Reconstruction for the potts model

AU - Sly, Allan

PY - 2009/11/9

Y1 - 2009/11/9

N2 - The reconstruction problem on the tree plays a key role in several important computational problems. Deep conjectures in statistical physics link the reconstruction problem to properties of random constraint satisfaction problems including random k-SAT and random colourings of random graphs. At this precise threshold the space of solutions is conjectured to undergo a phase transition from a single collected mass to exponentially many small clusters at which point local search algorithm must fail. In computational biology the reconstruction problem is central in phylogenetics. It has been shown [17] that solvability of the reconstruction problem is equivalent to phylogenetic reconstruction with short sequences for the binary symmetric model. Rigorous reconstruction thresholds, however, have only been established in a small number of models. We confirm conjectures made by Mezard and Montanari for the Potts models proving the first exact reconstruction threshold in a non-binary model establishing the so-called Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree. We further establish that the Kesten-Stigum bound is not tight for the q-state Potts model when q ≥ 5. Moreover, we determine asymptotics for these reconstruction thresholds.

AB - The reconstruction problem on the tree plays a key role in several important computational problems. Deep conjectures in statistical physics link the reconstruction problem to properties of random constraint satisfaction problems including random k-SAT and random colourings of random graphs. At this precise threshold the space of solutions is conjectured to undergo a phase transition from a single collected mass to exponentially many small clusters at which point local search algorithm must fail. In computational biology the reconstruction problem is central in phylogenetics. It has been shown [17] that solvability of the reconstruction problem is equivalent to phylogenetic reconstruction with short sequences for the binary symmetric model. Rigorous reconstruction thresholds, however, have only been established in a small number of models. We confirm conjectures made by Mezard and Montanari for the Potts models proving the first exact reconstruction threshold in a non-binary model establishing the so-called Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree. We further establish that the Kesten-Stigum bound is not tight for the q-state Potts model when q ≥ 5. Moreover, we determine asymptotics for these reconstruction thresholds.

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=70350682009&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350682009&partnerID=8YFLogxK

U2 - 10.1145/1536414.1536493

DO - 10.1145/1536414.1536493

M3 - Conference contribution

AN - SCOPUS:70350682009

SN - 9781605585062

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 581

EP - 590

BT - STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing

T2 - 41st Annual ACM Symposium on Theory of Computing, STOC '09

Y2 - 31 May 2009 through 2 June 2009

ER -