Reconstruction for the Potts model

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 [Mossel 04] that solvability of the reconstruction problem is equivalent to phylogenetic reconstruction with short sequences for the binary symmetric model.

Authors

• Allan Sly

Keywords

• Potts model
• reconstruction