Efficient parallel Ising samplers via localization schemes

DOI10.4230/LIPICS.APPROX/RANDOM.2025.46MaRDI QIDQ7346876zbMATH OpenFDO

Authors Xiaoyu Chen, Hongyang Liu, Yitong Yin, Xinyuan Zhang

Publication date 11 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2025.46

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A Near-Linear Time Sampler for the Ising Model with External Field
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A spectral condition for spectral gap: fast mixing in high-temperature Ising models
• An Information-Theoretic View of Stochastic Localization
• An O(logn) parallel connectivity algorithm
• Approximating the Permanent
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Dynamic Sampling from Graphical Models
• Entropic independence: optimal mixing of down-up random walks
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 7561278 (Why is no real title available?)
• scientific article; zbMATH DE number 7788465 (Why is no real title available?)
• Independent sets versus perfect matchings
• Localization schemes: a framework for proving mixing bounds for Markov chains (extended abstract)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On sampling from Ising models with spectral constraints
• Optimal mixing for two-state anti-ferromagnetic spin systems
• Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation
• Parallel discrete sampling via continuous walks
• Parallel Merge Sort
• Parallelising Glauber dynamics
• Parallelize single-site dynamics up to Dobrushin criterion
• Polynomial-Time Approximation Algorithms for the Ising Model
• Rapid mixing of Glauber dynamics via spectral independence for all degrees
• Sampling arborescences in parallel
• Simple parallel algorithms for single-site dynamics
• Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
• What can be sampled locally?

This page was built for publication: Efficient parallel Ising samplers via localization schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346876)