{"ID":6620479,"CreatedAt":"2026-07-15T01:01:48.440468303Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.12348","arxiv_id":"2607.12348","title":"Parallel Sampling from the Ising $p$-Spin Model","abstract":"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 $\\{\\pm 1\\}^n$. 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 $\\varepsilon \u003e 0$, this algorithm runs in $n^{\\tfrac{1}{3}}\\operatorname{polylog}(\\tfrac{n}{\\varepsilon})$ parallel time with $\\operatorname{poly}(n, \\log(\\tfrac{1}{\\varepsilon}))$ work, and outputs a sample whose law is $\\varepsilon$-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 $\\varepsilon \u003e \\varepsilon_n$, takes $\\operatorname{polylog}(\\tfrac{n}{\\varepsilon})$ parallel time and $\\operatorname{poly}(\\tfrac{n}{\\varepsilon})$ work to produce a sample that is $\\varepsilon$-close to the $p$-spin measure in the normalized 2-Wasserstein metric. Here, $\\varepsilon_n \u003e 0$ is a threshold that goes to $0$ as $n \\to \\infty$. Our result constitutes a doubly exponential improvement in the $\\varepsilon$ dependence of the runtime and an exponential improvement in the $\\varepsilon$ dependence of the total work when compared to naïve ASL, whose runtime scales as $\\exp(\\operatorname{poly}(\\tfrac{1}{\\varepsilon}))$.","short_abstract":"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 $\\{\\pm 1\\}^n$. We propose two different algorithms for this problem, corresponding to two different regimes of accuracy. Our first algorithm is a pa...","url_abs":"https://arxiv.org/abs/2607.12348","url_pdf":"https://arxiv.org/pdf/2607.12348v1","authors":"[\"Nima Anari\",\"Aniket Das\",\"Alireza Haqi\"]","published":"2026-07-14T04:48:40Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DC\"]","methods":"[]","has_code":false}