2026-09-10T09:44:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27788 2026-09-09T12:19:39Z ddc:004 open_access

Parallel Sampling from the Ising p-Spin Model Anari, Nima Das, Aniket Haqi, Alireza spin glasses parallel sampling Glauber dynamics stochastic localization We study the parallel complexity of sampling from the high-temperature Ising mixed p-spin Gibbs measure, a canonical instance of a mean-field spin glass on the hypercube {±1}ⁿ. We propose two different algorithms for this problem, corresponding to two different regimes of accuracy. Our first algorithm is a parallel implementation of a Markov chain known as block dynamics, combined with an approximate rejection sampling step that uses an Ising model in a novel way as a proposal distribution to approximate the quadratic interaction terms of the p-spin Hamiltonian. For any ε > 0, this algorithm runs in n^{1/3} polylog(n/ε) parallel time with poly(n/ε) work, and outputs a sample whose law is ε-close to the p-spin measure in total variation distance. Our second algorithm uses Picard iterations to parallelize the Algorithmic Stochastic Localization (ASL) process of El Alaoui, Montanari, and Sellke (2025), and for any ε > ε_n, takes polylog(n/ε) parallel time and poly(n/ε) work to produce a sample that is ε-close to the p-spin measure in the normalized 2-Wasserstein metric. Here, ε_n > 0 is a threshold that goes to 0 as n → ∞. Our result constitutes a doubly exponential improvement in the ε dependence of the runtime and an exponential improvement in the ε dependence of the total work when compared to naïve ASL, whose runtime scales as exp(poly(1/ε)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nima Anari and Aniket Das and Alireza Haqi 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.71 urn:nbn:de:0030-drops-277889 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.71 eng https://creativecommons.org/licenses/by/4.0/legalcode