Reconstruction for the potts model

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
Pages581-590
Number of pages10
DOIs
StatePublished - Nov 9 2009
Externally publishedYes
Event41st Annual ACM Symposium on Theory of Computing, STOC '09 - Bethesda, MD, United States
Duration: May 31 2009Jun 2 2009

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other41st Annual ACM Symposium on Theory of Computing, STOC '09
CountryUnited States
CityBethesda, MD
Period5/31/096/2/09

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Theory

Fingerprint Dive into the research topics of 'Reconstruction for the potts model'. Together they form a unique fingerprint.

Cite this