Cover Image

Spectral Independence and Local-to-Global Techniques for Optimal Mixing of Markov Chains

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Zongchen, Stefankovic, Daniel, Vigoda, Eric
Format:	Preprint
Published:	2023
Subjects:	Discrete Mathematics Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Spectral Independence via Stability and Applications to Holant-Type Problems
by: Chen, Zongchen, et al.
Published: (2021)

Critical window for approximate counting in dense Ising models
by: Galanis, Andreas, et al.
Published: (2026)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
by: Efthymiou, Charilaos, et al.
Published: (2023)

Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
by: Carlson, Charlie, et al.
Published: (2024)

Sampling Simultaneous Edge-Colorings
by: Furtado-Tiwari, Ezra, et al.
Published: (2026)

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
by: Jain, Vishesh, et al.
Published: (2026)

Faster Mixing of the Jerrum-Sinclair Chain
by: Chen, Xiaoyu, et al.
Published: (2025)

Flip Dynamics for Sampling Colorings: Improving $(11/6-ε)$ Using a Simple Metric
by: Carlson, Charlie, et al.
Published: (2024)

Strong spatial mixing for colorings on trees and its algorithmic applications
by: Chen, Zongchen, et al.
Published: (2023)

Phase Transitions via Complex Extensions of Markov Chains
by: Liu, Jingcheng, et al.
Published: (2024)

Multicoloured Hardcore Model: Fast Mixing and Queueing
by: Olesker-Taylor, Sam
Published: (2024)

Logarithmic Mixing of Random Walks on Dynamical Random Cluster Models
by: Galanis, Andreas, et al.
Published: (2026)

Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence
by: Feng, Weiming, et al.
Published: (2025)

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
by: Blanca, Antonio, et al.
Published: (2022)

Cliques, Chromatic Number, and Independent Sets in the Semi-random Process
by: Gamarnik, David, et al.
Published: (2023)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
by: Bansal, Nikhil, et al.
Published: (2025)

Improved Distributed Algorithms for Random Colorings
by: Carlson, Charlie, et al.
Published: (2023)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
by: Galanis, Andreas, et al.
Published: (2023)

Probability-graphons: Limits of large dense weighted graphs
by: Abraham, Romain, et al.
Published: (2023)

Noise sensitivity on affine Weyl groups
by: Tanaka, Ryokichi
Published: (2024)

Matchings on Random Regular Hypergraphs
by: Li, Zhongyang
Published: (2021)

Theory of Stochastic Drift
by: Kötzing, Timo
Published: (2024)

Cutoff for congestion dynamics and related generalized exclusion processes
by: Tanaka, Ryokichi
Published: (2025)

Subtractive random forests
by: Broutin, Nicolas, et al.
Published: (2022)

The Careless Coupon Collector's Problem
by: Cruciani, Emilio, et al.
Published: (2026)

Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs
by: Austin, Henry, et al.
Published: (2026)

On sampling diluted Spin Glasses using Glauber dynamics
by: Efthymiou, Charilaos, et al.
Published: (2024)

Towards an Optimal Contention Resolution Scheme for Matchings
by: Nuti, Pranav, et al.
Published: (2022)

A Tight Bound on Localization of Electrical Flows
by: Gurel-Gurevich, Ori, et al.
Published: (2026)

Geometric Bounds on the Fastest Mixing Markov Chain
by: Olesker-Taylor, Sam, et al.
Published: (2021)

From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP
by: Gurvits, Leonid, et al.
Published: (2023)

Zero-One Laws for Random Feasibility Problems
by: Altschuler, Dylan J.
Published: (2023)

A binomial random multigraph
by: Pelekis, Christos
Published: (2023)

Talagrand's convolution conjecture up to loglog via perturbed reverse heat
by: Chen, Yuansi
Published: (2025)

Canonical labelling of random regular graphs
by: Isaev, Mikhail, et al.
Published: (2026)

On the Asymptotics of the Connectivity Probability of Random Bipartite Graphs
by: Chinyaev, Boris
Published: (2025)

A threshold for online balancing of sparse i.i.d. vectors
by: Altschuler, Dylan J., et al.
Published: (2025)

Speeding up random walk mixing by starting from a uniform vertex
by: Díaz, Alberto Espuny, et al.
Published: (2022)

Limit Laws for Critical Dispersion on Complete Graphs
by: De Ambroggio, Umberto, et al.
Published: (2024)

Shotgun assembly of random graphs
by: Johnston, Tom, et al.
Published: (2022)