Pith. sign in

REVIEW 1 major objections 5 minor 39 references

Efficient Parallel Ising Samplers via Localization Schemes

T0 review · 1 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that ferromagnetic Ising models with external fields and Ising models with contracting interaction matrices admit the first RNC Gibbs samplers, running in polylogarithmic parallel time with polynomial work.

desk verdict The random-cluster/ferromagnetic sampler is strong and likely correct, but the restricted Gaussian proof in Appendix D has a false universal ratio bound that needs repair before Theorem 1.3 stands. read the letter →

arxiv 2505.05185 v1 pith:6KYWXXSJ submitted 2025-05-08 cs.DS

Xiaoyu Chen , Hongyang Liu , Yitong Yin , Xinyuan Zhang This is my paper · ORCID
classification cs.DS MSC 68W1068Q2582B2060J22
keywords IsingmodelparallelsamplingRNCfielddynamicsrandomclusterstochasticlocalizationrestrictedGaussianGibbs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that two regimes of the Ising model that were previously only known to be sequentially samplable are in fact samplable in randomized polylogarithmic parallel time (RNC). The first regime is ferromagnetic Ising with inverse temperature at least $1+\delta$ and external fields at most $1-\delta$; the second is any Ising model whose interaction matrix satisfies $\tfrac{\eta}{2}I \preceq J \preceq (1-\tfrac{\eta}{2})I$ with arbitrary external fields. For both, the proposed algorithms use polylogarithmic depth and polynomial total work, and the first regime also yields an RNC approximation of the partition function via annealing. The significance is that these are claimed to be the first RNC samplers in either regime, connecting a classically tractable sampling problem to the broader question of which sequential sampling tasks admit fast parallel algorithms.

What carries the argument

Negative-field localization and its induced field dynamics: a global Markov chain on edge subsets whose update adds each element to a random set with probability $\theta$ and then resamples from a tilted posterior, mixing in polylogarithmically many steps because the tilt drives the model into a low-temperature regime. Stochastic localization and its induced restricted Gaussian dynamics: a two-step chain on spin configurations alternating $y_i \sim \mathcal{N}(x_{i-1}, J^{-1})$ with resampling from a posterior that becomes a product distribution. Two further mechanisms carry the parallel efficiency: the coupling-with-stationarity criterion, which relaxes the Dobrushin condition needed for the parallel Glauber simulation, and parallel Langevin Monte Carlo, which supplies the Gaussian noising samples.

What would settle it

Set $n > 10/\eta$, take $J = 0.5I + 0.4 uu^\top$ with $u$ a unit vector, and compare $x$ with $u^\top x = \sqrt{n}$ against $y$ with $u^\top y = 0$. Then $\mu(x)/\mu(y) = \exp(0.2n) > \exp(2/\eta)$, contradicting the Appendix D bound used in the mixing proof; checking whether the algorithm's argument survives such a $J$ would settle the matter.

Watch

Extended reading notes

Core claim

The central discovery is that localization schemes, originally developed as tools for proving rapid mixing, can be turned into efficient parallel samplers. For ferromagnetic models, the paper simulates the field dynamics of the random-cluster model: each step adds edges to a random set with probability $\theta$ and then resamples from a tilted low-temperature random-cluster distribution. The resampling step is implemented by Glauber dynamics, and a new “coupling with stationarity” criterion replaces the Dobrushin condition, allowing the parallel Glauber simulation to remain faithful in this low-temperature regime. For contracting interactions, the paper simulates restricted Gaussian dynamics, alternating Gaussian noise with covariance $J^{-1}$ and a product-form posterior resampling, with the Gaussian step handled by a parallel log-concave sampler. The two theorems state $\bigl(\epsilon^{-1}\log n \cdot \log n\bigr)^{O_\delta(1)}$ parallel time for ferromagnetic models and $O_\eta(\log^4(n/\epsilon))$ parallel time for contracting interactions, both with polynomial processors.

Load-bearing premise

For Theorem 1.3, the load-bearing premise is the Appendix D assertion that, whenever $\tfrac{\eta}{2}I \preceq J \preceq (1-\tfrac{\eta}{2})I$, every configuration is at most $\exp(2/\eta)$ times as likely as any other, since that is what turns entropy decay into an $O_\eta(\log(n/\epsilon))$ iteration count for arbitrary external fields.

Editorial extensions

If this is right

  • A ferromagnetic Ising partition function can be approximated to $(1\pm\epsilon)$ in RNC by running the work-efficient parallel annealing algorithm of [LYZ24] on top of the Theorem 1.1 sampler.
  • The random-cluster sampler of Theorem 1.2 inherits the same polylogarithmic depth and polynomial work, so improvements for one model transfer to the other through the Edwards–Sokal coupling.
  • Under $\|J\|_2 \le 1-\eta$, adding a constant diagonal shift $J' = J + CI$ produces an instance satisfying Theorem 1.3, so the sampler covers every contracting interaction matrix for which Glauber dynamics is known to mix rapidly.
  • The coupling-with-stationarity criterion is stated for arbitrary Boolean-domain Glauber dynamics, making the parallel simulation theorem a general tool rather than a random-cluster-specific result.
  • The Gaussian noising step is the only component of the contracting-interaction sampler using expensive parallel sampling, so a faster parallel Gaussian oracle would speed up the entire sampler proportionally.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the contracting-interaction theorem is only as strong as the Appendix D assertion that $\mu(x)/\mu(y) \le \exp(2/\eta)$ for all $x,y$; this bound is directly checkable, and its failure would force a different treatment of the external field in the mixing argument.
  • Editorial inference: a natural test is to push the field-dynamics sampler closer to critical temperature by replacing the denoising subroutine with another rapidly mixing chain, since the localization tilt only needs to make that subroutine fast.
  • Editorial inference: the same two-phase template—noise through a log-concave channel, denoise from a product posterior—may yield RNC samplers for other Gibbs distributions with log-concave interaction structure, such as bounded continuous spin systems.
  • Editorial inference: because Theorem 1.2 is the engine behind Theorem 1.1, the edge cases $p\to 1$ and $\lambda\to 1$ are the bottlenecks; eliminating them would extend the ferromagnetic sampler to the full ferromagnetic region.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper proposes two parallel Ising samplers. The first targets ferromagnetic Ising models with external fields by sampling from the associated random cluster model: it simulates field dynamics (negative-field localization) and uses a new 'coupling with the stationary distribution' criterion to parallelize the Glauber dynamics used in each denoising step. The second targets Ising models whose interaction matrix J satisfies ηI/2 ⪯ J ⪯ (1−η/2)I with arbitrary external fields, by simulating restricted Gaussian dynamics (stochastic localization); the Gaussian noising step is implemented by a parallel Langevin algorithm and the denoising step by product-form sampling. Theorems 1.1 and 1.2 state polylogarithmic-depth samplers for the ferromagnetic/random-cluster regimes, and Theorem 1.3 states an O_η(log^4(n/ε))-depth sampler for the contracting-matrix regime. The random-cluster result is also used to approximate the partition function via parallel annealing.

Significance. If the theorems are correct, the random-cluster/ferromagnetic part would be the first RNC sampler for ferromagnetic Ising models outside the high-temperature uniqueness region, and the contracting-matrix result would match the spectral threshold ||J||_2<1 for which sequential Glauber dynamics is rapidly mixing. The paper's main technical novelty, Condition 1, is a genuinely useful relaxation of the Dobrushin condition used in earlier parallel single-site dynamics, and the random-cluster half is presented with detailed proofs, explicit parameter choices, and a nontrivial good event taken from prior work; this part appears internally consistent. The restricted-Gaussian part is less complete: one inequality used in the proof of Item 3 in Appendix D is false, so Theorem 1.3 is not justified as written, although the gap appears repairable rather than fatal.

major comments (1)
  1. [Appendix D, verification of Item 3] The assertion 'Since 0≺η/2 I ⪯ J ⪯ (1−η/2) I, it follows that for all x,y ∈ {±1}^n, μ(x)/μ(y) ≤ exp(2/η)' is false. A concrete counterexample is η=0.2, u=1_V/√n, J=0.5I+0.4uu^T, h=0, x=all-plus, and y any configuration with u^T y=0 (e.g., half plus and half minus). Then η/2 I ⪯ J ⪯ (1−η/2) I holds, but log(μ(x)/μ(y)) = (1/2)(0.9n − 0.5n) = 0.2n, which exceeds 2/η = 10 for n>50. The proof of Item 3 uses this false bound to conclude 1/μ(x0) ≤ 2^n exp(2/η) and then sets T_RGD = O_η(log(n/ε)), so the proof of Theorem 1.3 is incomplete as written. The theorem may still be true; for instance, initializing x0 = sign(h) gives |x^T Jx − x0^T Jx0| ≤ 4n and h^T(x − x0) ≤ 0 for all x, hence 1/μ(x0) ≤ 2^n e^{2n}, and the same T_RGD = O_η(log(n/ε)) follows. Please repair Item 3 accordingly.
minor comments (5)
  1. [Theorems 1.1 and 1.2] The stated parallel-time bounds (ε^{-1} log n · log n)^{O_δ(1)} are polynomial in 1/ε, which is weaker than what the analysis in Table 1 and Appendix C.1 appears to give for polynomially small ε; please state the sharpest bound that follows from the parameter choices, or clarify explicitly that RNC is understood with ε treated as a constant.
  2. [Lemma 3.2] The Edwards-Sokal coupling is stated for λ ∈ (0,1), while Theorem 1.1 allows λ_v = 0; please state the boundary case explicitly or justify it by a limiting argument, since the random-cluster component inclusion probability is 0 when a component contains a vertex with λ_v = 0.
  3. [Appendix D, Item 1] The algorithm samples from N(x_{i−1}, J^{-1}), but the Langevin implementation is described for N(0, J^{-1}); please state explicitly that one samples Z from the latter and returns x_{i−1}+Z.
  4. [Appendix D, denoising step] In the expansion of the denoising distribution, 'h⊺σ' should read 'h⊺x'; also, the factor exp(−(1/2)y_i^T J y_i) is independent of x and cancels in the conditional distribution, which is worth stating explicitly.
  5. [Appendix C.1] There is a typo, 'teriminates' for 'terminates' in Proposition C.1.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation; imported mixing theorems are used as black-box prior results, and the Appendix D defect is a soundness gap, not a circularity step.

full rationale

The derivation chain is not circular. The random-cluster/ferromagnetic sampler uses known mixing bounds as black boxes: Lemma C.4 (field dynamics mixing) and Lemma B.1 (low-temperature random-cluster Glauber mixing) are quoted from [CZ23], a separate SODA 2023 paper with published proofs; the paper's new coupling-with-stationary criterion (Condition 1, Theorem 4.1) analyzes the parallel simulation rather than re-deriving those mixing times. Similarly, Theorem 1.3's Item 3 imports the entropy decay of restricted Gaussian dynamics from [CE22, CCYZ24] as a black-box theorem, while the paper's own contribution is the parallel Langevin implementation and the product-structure denoising step. No fitted parameter is renamed as a prediction, and no definition is stated in terms of the target quantity. I do flag a non-circular correctness gap in Appendix D: the assertion that `0 ≺ η/2 I ⪯ J ⪯ (1−η/2)I` implies `µ(x)/µ(y) ≤ exp(2/η)` for all x,y is false; for example, with J = 0.5I + 0.4uu^T, u = 1_V/√n, x = all +1, and y with half +1/half −1, the ratio is exp(0.2n), exceeding exp(2/η) for n > 50. This invalidates the displayed `TRGD` formula as written, but it is a missing-support or proof issue, not a circularity issue, and it does not raise the circularity score.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new particles, fields, or physical entities; it uses existing Markov chains (field dynamics and restricted Gaussian dynamics) and known algorithmic primitives. The only hand-chosen quantities are the algorithmic parameters listed above, which are set analytically rather than fitted to data. The key external assumptions are prior mixing theorems, some self-cited, used as black boxes.

free parameters (5)
  • theta = e^{-100} exp(10 log(epsilon/2)/log n) exp(-140(1-lambda_max)^{-2}) p_min/log n
    Noise probability in field dynamics; chosen by hand to satisfy the mixing and parameter bounds in the proof.
  • N0 = max{exp(60(1-lambda_max)^{-2}), 3/p_min, sqrt(log(2/epsilon^2)/log n)}
    Brute-force threshold; fixed analytically so that the inequalities in Lemma C.3 hold.
  • TFD = ceil((e/theta)^{5(1-lambda_max)^{-2}}(2 log n + log log(2/p_min) + log(2/epsilon^2)))
    Number of field dynamics rounds; taken from the CZ23 mixing bound.
  • TGD = ceil(2m(log m + log(8 TFD/epsilon)))
    Number of Glauber steps simulated in parallel; chosen to satisfy Theorem 4.3.
  • TPA = ceil(3 log(8 TGD TFD/epsilon))
    Number of parallel stabilization rounds; chosen to make the parallel simulation error small.
assumptions (5)
  • domain assumption The Ising and random cluster weight definitions (Eqs. 1 and 2) define the target distributions.
    The algorithms sample from these standard statistical physics measures; the paper does not derive these definitions.
  • standard math Edwards-Sokal coupling (Lemma 3.2, from FGW22) maps random cluster samples to Ising samples.
    Used to derive Theorem 1.1 from the random cluster sampler Theorem 1.2.
  • standard math Rapid mixing of field dynamics for low-temperature random clusters (CZ23, Lemma C.4).
    Provides the TFD mixing bound used in Algorithm 1; this is a prior result with overlapping authors.
  • standard math Entropy decay of restricted Gaussian dynamics for ||J||_2 <= 1 - delta (CE22, CCYZ24, Theorem D.2).
    Provides the TRGD mixing bound for Algorithm 3; CCYZ24 has overlapping authors.
  • standard math Parallel Langevin Monte Carlo (ACV24, Theorem D.1) samples from Gaussian N(0,J^{-1}) efficiently.
    Implements the noising step of Algorithm 3 in parallel.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Parallel Ising Samplers via Localization Schemes." pith.science (2026). https://pith.science/paper/6KYWXXSJ

@misc{pith2026250505185,
  author       = {Pith},
  title        = {Pith review of: Efficient Parallel Ising Samplers via Localization Schemes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6KYWXXSJ}},
  note         = {Machine review of arXiv:2505.05185}
}
abstract

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\|_2<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 \emph{field dynamics} induced by \emph{negative-field localization}, and \emph{restricted Gaussian dynamics} induced by \emph{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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 27 canonical work pages

  1. [1]

    Quadratic speedups in parallel sampling from determinantal distributions

    Nima Anari, Callum Burgess, Kevin Tian, and Thuy-Duong Vuong. Quadratic speedups in parallel sampling from determinantal distributions. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures , pages 367--377, 2023

    work page 2023

  2. [2]

    Fast parallel sampling under isoperimetry

    Nima Anari, Sinho Chewi, and Thuy - Duong Vuong. Fast parallel sampling under isoperimetry. In Shipra Agrawal and Aaron Roth, editors, The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada , volume 247 of Proceedings of Machine Learning Research , pages 161--185. PMLR , 2024

    work page 2023

  3. [3]

    Parallel sampling via counting

    Nima Anari, Ruiquan Gao, and Aviad Rubinstein. Parallel sampling via counting. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 , pages 537--548. ACM , 2024

    work page 2024

  4. [4]

    Parallel discrete sampling via continuous walks

    Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu. Parallel discrete sampling via continuous walks. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 103--116, 2023

    work page 2023

  5. [5]

    Sampling arborescences in parallel

    Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild. Sampling arborescences in parallel. In ITCS , volume 185 of LIPIcs , pages 83:1--83:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2021

    work page 2021

  6. [6]

    Entropic independence i: Modified log-sobolev inequalities for fractionally log-concave distributions and high-temperature ising models

    Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Entropic independence i: Modified log-sobolev inequalities for fractionally log-concave distributions and high-temperature ising models. arXiv preprint arXiv:2106.04105 , 2021

    arXiv 2021

  7. [7]

    Entropic independence: optimal mixing of down-up random walks

    Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy - Duong Vuong. Entropic independence: optimal mixing of down-up random walks. In STOC , pages 1418--1430. ACM , 2022

    2022

  8. [8]

    Trickle-down in localization schemes and applications

    Nima Anari, Frederic Koehler, and Thuy-Duong Vuong. Trickle-down in localization schemes and applications. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1094--1105, 2024

    2024

Show all 39 references
  1. [9]

    Rapid mixing at the uniqueness threshold

    Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing at the uniqueness threshold. arXiv preprint arXiv:2411.03413 , 2024

    2024

  2. [10]

    Localization schemes: A framework for proving mixing bounds for markov chains (extended abstract)

    Yuansi Chen and Ronen Eldan. Localization schemes: A framework for proving mixing bounds for markov chains (extended abstract). In FOCS , pages 110--122. IEEE , 2022

    2022

  3. [11]

    Rapid mixing of G lauber dynamics via spectral independence for all degrees

    Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Rapid mixing of G lauber dynamics via spectral independence for all degrees. In FOCS , pages 137--148, 2021

    2021

  4. [12]

    Optimal mixing for two-state anti-ferromagnetic spin systems

    Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Optimal mixing for two-state anti-ferromagnetic spin systems. In FOCS , pages 588--599. IEEE , 2022

    2022

  5. [13]

    Parallel merge sort

    Richard Cole. Parallel merge sort. SIAM J. Comput. , 17(4):770--785, 1988

    1988

  6. [14]

    A near-linear time sampler for the ising model with external field

    Xiaoyu Chen and Xinyuan Zhang. A near-linear time sampler for the ising model with external field. In SODA , pages 4478--4503. SIAM, 2023

    2023

  7. [15]

    A random polynomial-time algorithm for approximating the volume of convex bodies

    Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM) , 38(1):1--17, 1991

    1991

  8. [16]

    An information-theoretic view of stochastic localization

    Ahmed El Alaoui and Andrea Montanari. An information-theoretic view of stochastic localization. IEEE Trans. Inform. Theory , 68(11):7423--7426, 2022

    2022

  9. [17]

    A spectral condition for spectral gap: fast mixing in high-temperature ising models

    Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. A spectral condition for spectral gap: fast mixing in high-temperature ising models. Probability Theory and Related Fields , pages 1--17, 2021

    2021

  10. [18]

    Edwards and Alan D

    Robert G. Edwards and Alan D. Sokal. Generalization of the F ortuin- K asteleyn- S wendsen- W ang representation and M onte C arlo algorithm. Phys. Rev. D (3) , 38(6):2009--2012, 1988

    2009

  11. [19]

    A simple parallel and distributed sampling technique: Local glauber dynamics

    Manuela Fischer and Mohsen Ghaffari. A simple parallel and distributed sampling technique: Local glauber dynamics. In 32nd International Symposium on Distributed Computing (DISC 2018) , volume 121, pages 26--1. Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2018

    2018

  12. [20]

    Sampling from the ferromagnetic ising model with external fields

    Weiming Feng, Heng Guo, and Jiaheng Wang. Sampling from the ferromagnetic ising model with external fields. arXiv preprint arXiv:2205.01985 [v1] , 2022

    2022 arXiv

  13. [21]

    Distributed metropolis sampler with optimal parallelism

    Weiming Feng, Thomas P Hayes, and Yitong Yin. Distributed metropolis sampler with optimal parallelism. In SODA , pages 2121--2140. SIAM, 2021

    2021

  14. [22]

    What can be sampled locally? In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing ( PODC ) , pages 121--130, 2017

    Weiming Feng, Yuxin Sun, and Yitong Yin. What can be sampled locally? In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing ( PODC ) , pages 121--130, 2017

    2017

  15. [23]

    Dynamic sampling from graphical models

    Weiming Feng, Nisheeth K Vishnoi, and Yitong Yin. Dynamic sampling from graphical models. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages 1070--1081, 2019

    2019

  16. [24]

    Parallelising glauber dynamics

    Lee Holden. Parallelising glauber dynamics. RANDOM 2024 , 2023

    2024

  17. [25]

    Hayes and Eric Vigoda

    Thomas P. Hayes and Eric Vigoda. Coupling with the stationary distribution and improved sampling for colorings and independent sets. Ann. Appl. Probab. , 16(3):1297--1318, 2006

    2006

  18. [26]

    Beitrag zur theorie des ferro-und paramagnetismus

    Ernst Ising. Beitrag zur theorie des ferro-und paramagnetismus . PhD thesis, Grefe & Tiedemann Hamburg, 1924

    1924

  19. [27]

    An introduction to parallel algorithms

    Joseph J \'e J \'e . An introduction to parallel algorithms. Reading, MA: Addison-Wesley , 10:133889, 1992

    1992

  20. [28]

    Approximating the permanent

    Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput. , 18(6):1149--1178, 1989

    1989

  21. [29]

    Polynomial-time approximation algorithms for the I sing model

    Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the I sing model. SIAM J. Comput. , 22(5):1087--1116, 1993

    1993

  22. [30]

    A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

    Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM) , 51(4):671--697, 2004

    2004

  23. [31]

    Levin, Malwina J

    David A. Levin, Malwina J. Luczak, and Yuval Peres. Glauber dynamics for the mean-field I sing model: cut-off, critical power law, and metastability. Probab. Theory Related Fields , 146(1-2):223--265, 2010

    2010

  24. [32]

    Levin, Yuval Peres, and Elizabeth L

    David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times . American Mathematical Society, Providence, RI, 2017

    2017

  25. [33]

    Structured logconcave sampling with a restricted gaussian oracle

    Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted gaussian oracle. In The Annual Conference on Learning Theory (COLT) , pages 2993--3050, 2021

    2021

  26. [34]

    Simple parallel algorithms for single-site dynamics

    Hongyang Liu and Yitong Yin. Simple parallel algorithms for single-site dynamics. In STOC , pages 1431--1444. ACM, 2022

    2022

  27. [35]

    Parallelize single-site dynamics up to dobrushin criterion

    Hongyang Liu and Yitong Yin. Parallelize single-site dynamics up to dobrushin criterion. J. ACM , 72(1), January 2025

    2025

  28. [36]

    Work-efficient parallel counting via sampling

    Hongyang Liu, Yitong Yin, and Yiyao Zhang. Work-efficient parallel counting via sampling. arXiv preprint arXiv:2408.09719 , 2024

    2024 arXiv

  29. [37]

    Matching is as easy as matrix inversion

    Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In STOC , pages 345--354. ACM, 1987

    1987

  30. [38]

    An o (log n) parallel connectivity algorithm

    Yossi Shiloach and Uzi Vishkin. An o (log n) parallel connectivity algorithm. Technical report, Computer Science Department, Technion, 1980

    1980

  31. [39]

    Independent sets versus perfect matchings

    Shang-Hua Teng. Independent sets versus perfect matchings. Theoret. Comput. Sci. , 145(1-2):381--390, 1995

    1995

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.