2026-07-23T19:18:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24412 2025-12-12T15:01:37Z ddc:004 open_access

Efficient Parallel Ising Samplers via Localization Schemes Chen, Xiaoyu Liu, Hongyang Yin, Yitong Zhang, Xinyuan Localization scheme parallel sampling Ising model We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficiency, with polylogarithmic depth and polynomial total work, and are applicable to Ising models in the following regimes: (1) Ferromagnetic Ising models with external fields; (2) Ising models with interaction matrix J of operator norm ‖J‖₂ < 1. Our parallel Gibbs sampling approaches are based on localization schemes, which have proven highly effective in establishing rapid mixing of Gibbs sampling. In this work, we employ two such localization schemes to obtain efficient parallel Ising samplers: the field dynamics induced by negative-field localization, and restricted Gaussian dynamics induced by stochastic localization. This shows that localization schemes are powerful tools, not only for achieving rapid mixing but also for the efficient parallelization of Gibbs sampling. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiaoyu Chen and Hongyang Liu and Yitong Yin and Xinyuan Zhang 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.46 urn:nbn:de:0030-drops-244129 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.46 eng https://creativecommons.org/licenses/by/4.0/legalcode