Results 181 - 190 of 24651
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$.
We study a refinement of the product replacement algorithm that is designed to output individual elements of a finite group $G$ in a random way. We show after how many steps, the distribution of the output is close to uniform on $G$. The proof proceeds via spectral gap estimates and uses computer assisted calculations. This is a joint work with Michał Marcinkowski.
The curvature of a graph is basically a measure of local geometry, with albeit too many different definitions. Here we will focus on how the discrete curvature, as a locally defined invariant, has nontrivial global consequences ---- through its relations with eigenvalues, eigenvectors, edge expansions, optimal transport and clustering effects of graphs.
Amatya Sharma is a PhD candidate in Computer Science and Engineering at the University of Michigan, Ann Arbor. His research focuses on approximation algorithms, streaming algorithms, and parameterized complexity, with an emphasis on constraint satisfaction...
Entropic Ricci curvature, introduced by Erbar and Maas, provides a discrete analogue of Ricci curvature through displacement convexity of relative entropy in Wasserstein space. In this talk, we introduce the notion, emphasizing its local characterization through infinitesimal variations of entropy. We then discuss curvature estimates for concrete graph families. In particular, we present recent improvements for cycles and abelian Cayley graphs, obtaining sharper bounds.
Uniform sampling from a convex body is a classical problem in theoretical computer science, closely connected to randomized volume computation in the seminal work of Dyer, Frieze, and Kannan. In this talk, I will use this problem to motivate the geometric quantities that govern the mixing of uniform samplers and explain their connection to the Kannan–Lovász–Simonovits conjecture. I will then review stochastic localization as a tool for handling these quantities and walk through a simple argument that yields a sub-optimal (but still poly-logarithmic) bound.