ACO Seminar - Nitya Mani

— 4:00pm

Location:
In Person - Wean Hall 8220

Speaker:
NITYA MANI , Ph.D. Student, Department of Mathematics , Massachusetts Institute of Technology
https://www.mit.edu/~nmani/

Strong spatial mixing for colorings on trees and its algorithmic applications

Strong spatial mixing (SSM) is an important and widely studied quantitative notion of "correlation decay" for a variety of natural distributions arising in statistical physics and theoretical computer science. One of the most widely studied such distributions is the uniform distribution over proper q-colorings on a maximum degree Δ graph, μ. Provided that q ≥ Δ+1 , any such graph has at least one proper q-coloring that can be identified via e.g. a greedy search. It is a longstanding folklore conjecture that whenever q satisfies this minimal inequality, μ exhibits SSM and the correlations between the colors of vertices in a sample from μ decay exponentially fast in the graph distance between the vertices. However, even the specialization of this basic question to bounded-degree trees has remained wide open, highlighting how much there still is to learn about random colorings.

We essentially resolve the SSM conjecture on trees, holds for random q-colorings on trees of maximum degree Δ whenever q≥Δ+3. In the algorithmic direction, we use SSM on trees to establish optimal mixing of the Glauber dynamics (a classical Markov chain) for sampling q-colorings on graphs of maximum degree Δ and girth \girth whenever q≥Δ+3. We discuss failures of this style of reduction to extend more generally to all graphs. 

Includes joint work with Zongchen Chen, Kuikui Liu, and Ankur Moitra and with Kuikui Liu and Francisco Pernice.

4:00 pm → Jane Street sponsored Tea and Cookies in the Math Lounge. Bring your own mug if possible.

Event Website:
https://aco.math.cmu.edu/abs-24-25/apr17.html

Add event to Google
Add event to iCal