Ankur Moitra

Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications

Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution on proper q -colorings on...