Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications @SimonsInstitute
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications  @SimonsInstitute
Uploaded September 2026 | Updated November 2026, 4 days ago
Nitya Mani (Massachusetts Institute of Technology)
https://simons.berkeley.edu/talks/nitya-mani-massachusetts-institute-technology-2026-09-24
Local to Global Principles

Strong spatial mixing (SSM) is an important quantitative notion of correlation decay that has been surprisingly challenging to establish for many natural Gibbs distributions. Notably, it has been long conjectured that random $q$-colorings on $\Delta$-regular trees exhibit SSM whenever $q ≥ \Delta + 1$. We establish that for any $\Delta \ge 3$, SSM holds for random $q$-colorings on trees of maximum degree $\Delta$ whenever $q ≥ \Delta + 3$. Using this, we also establish optimal Glauber mixing for fixed $\Delta$ and $q ≥ \Delta + 3$ when the girth of the underlying graph is sufficiently large as a function of $\Delta$.
Strong Spatial Mixing for Colorings on Trees and its Algorithmic ApplicationsSpectral gap of 1D quantum Gibbs samplersSharp Bounds on Ground State Energy of the SYK ModelRare event analysis via stochastic optimal controlThe Pseudorandomness Toolkit (Part 2)Trickle-down Theorems for High-dimensional Expanders via Log-concave PolynomialsExpansion of higher-dimensional cubical complexes with application to quantum locally testable codesExponential Lower Bounds for 2-query Relaxed Locally Decodable CodesPseudorandom bits for low degree modular polynomialsLightning TalksAgent Arena: Causal Evaluations of Agents in the Real WorldHow did we miss the random purification channel?
Simons Institute for the Theory of Computing |

Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER