Regev's Reduction Reaches ReconstructionResearch Paper
Sampling from the Gibbs distribution of a spin glass at low temperature is a central primitive of statistical physics and optimization. For sparse random constraint systems, the question of which temperatures are reachable in polynomial time is usually tied to the dynamical glass transition, which Mézard and Montanari identified with a reconstruction…