Spectral independence, coupling, and the spectral gap of the Glauber dynamics

DOI10.1016/j.ipl.2022.106268OpenAlexW4220905732MaRDI QIDQ2671814

Thuy Duong Vuong, Vishesh Jain, Huy-Tuan Pham

Publication date: 3 June 2022

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.01201

zbMATH Keywords

analysis of algorithmsMCMCgraph coloringsspectral independence

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
• Local uniformity properties for glauber dynamics on graph colorings
• Approximating the Permanent
• Randomly Colouring Graphs with Girth Five and Large Maximum Degree
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
• Improved analysis of higher order random walks and applications

This page was built for publication: Spectral independence, coupling, and the spectral gap of the Glauber dynamics