Pith. sign in

REVIEW 5 minor 49 references

On sampling diluted Spin-Glasses with unbounded interactions

T0 review · 0 major / 5 minor · reviewed 2026-07-13 · grok-4.5

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

Pith's one-line read Glauber dynamics mixes in nearly linear time for typical diluted 2-spin glasses with Gaussian couplings up to β = 1/(4√d).

desk verdict First rapid-mixing result for Gaussian 2-spin glasses on G(n,d/n) via a new block partition and matrix-norm control of unbounded covariances; improves the Viana-Bray threshold as a byproduct. read the letter →

arxiv 2603.22432 v2 pith:4XGEM73V submitted 2026-03-23 cs.DM math.PR

Charilaos Efthymiou , Kostas Zampetakis This is my paper · ORCID
classification cs.DMmath.PR MSC 68W2060J1082B44
keywords spinglassesGlauberdynamicsmixingtimestochasticlocalisationdilutedmodelsunboundedinteractionsrandomgraphsViana-Braymodel
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

The paper shows that, on a typical sparse random graph G(n, d/n), the natural Markov chain for sampling from the 2-spin glass with unbounded Gaussian edge couplings mixes in time n to a power only slightly larger than 1, provided the inverse temperature is at most one-quarter the reciprocal square root of the average degree. The same bound improves the previous temperature threshold for the classical Viana-Bray model that uses only ±1 couplings. The argument works by combining a carefully designed block partition of the vertices (that isolates high-degree vertices and strong couplings inside small trees or unicyclic graphs) with a stochastic-localisation path that reduces the problem to a product measure while controlling entropy decay through matrix norms of the covariance. Because both degrees and interactions may be unbounded, earlier localisation schemes that assumed bounded entries do not apply; the new partition and the tailored norms are what make the entropy estimates close. A sympathetic reader cares because spin glasses appear in neural models, network inference and optimisation, and the result is the first rigorous rapid-mixing guarantee for the genuinely unbounded diluted case.

What carries the argument

The ε-block partition of the vertex set, built from aggregate squared influences Θ(u) = ∑_z anh^{2}(eta J_{uz}), together with a bespoke matrix norm that bounds the restricted covariance matrices on the multi-vertex blocks; these two ingredients let stochastic localisation control entropy decay even when both degrees and Gaussian couplings are unbounded.

What would settle it

Compute, for moderate n and several d, the empirical fraction of G(n,d/n) instances that admit an ε-block partition with the claimed diameter and boundary-influence properties; if that fraction stays bounded away from 1, the geometric premise fails.

Watch

Extended reading notes

Core claim

For every fixed d large enough and every inverse temperature β ≤ β_c(d) defined by d E[(tanh(γ eta_c))^{2}] = 1/4, a typical instance of the 2-spin model on G(n, d/n) has Glauber mixing time O(n^{1 + 25/√(log d)}) with probability 1-o(1). The same temperature window yields rapid mixing for the Viana-Bray model, improving the previous constant 0.18 to 0.25.

Load-bearing premise

That a typical random graph admits an ε-block partition in which every multi-vertex block is a small tree or unicyclic graph whose boundary vertices have only weak influence and whose possible short cycle sits far from the boundary.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper proves that for typical instances of the 2-spin model (Gaussian couplings) on G(n, d/n) with d = Θ(1) fixed and inverse temperature β ≤ β_c(d) (defined by d · E[(tanh(γ β_c))^{2}] = 1/4), Glauber dynamics mixes in time O(n^{1 + 25/√(log d)}) with probability 1-o(1). The same bound yields rapid mixing for the Viana-Bray model up to β ≤ 1/(4√d), improving the prior 0.18/√d threshold. The argument combines a new ε-block partition of vertices (built from aggregate squared influences Θ(u)) with stochastic localisation (building on Liu-Mohanty-Rajaraman-Wu), controlling entropy decay via bespoke matrix norms on all-paths trees of the (tree/unicyclic) multi-vertex blocks.

Significance. This is a solid technical advance on sampling diluted spin glasses. It is the first successful application of stochastic localisation to the fully unbounded setting (both degrees and Gaussian interactions), and the improved temperature range for Viana-Bray is a concrete quantitative gain over FOCS 2024. The elaborate block partition and the matrix-norm comparison that handle unbounded couplings are reusable tools. The result sits a factor-4 short of the conjectured reconstruction threshold, which the authors correctly flag as inherent to the current localisation scheme; the mixing-time exponent is not optimised but already polynomial. Machine-checked proofs are absent, yet the multi-section derivation is self-contained and invokes only standard facts (Chen-Eldan, random-graph geometry, comparison of Dirichlet forms).

minor comments (5)
  1. Abstract claims mixing time O(n^{1+Θ(1/√d)}) while Theorem 1.1 and the body give the sharper (and weaker) O(n^{1+25/√(log d)}). Align the two statements and note that the analysis likely yields 1+O(1/log d).
  2. Section 2 (Approach) and Definition 4.2: the secondary properties of ε-block vertices (single neighbour inside the block, Γ_e ≪ 1) are used crucially later but are only sketched; a short formal lemma collecting them would help the reader.
  3. Theorem 6.2 and the choice of shift parameters δ, ζ: the concrete numerical values (e.g., ε/100, ζ = 1/(10c)) appear without a short sensitivity discussion; a remark that any sufficiently small positive constants work would clarify robustness.
  4. Several places (e.g., after (6.6), (10.19)) leave absolute constants unoptimised; a single sentence stating that no attempt was made to minimise the 25 would be useful.
  5. Typographical: “corollory” (p. 11), “unicylic” (several places), and occasional missing spaces around · and √.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the mixing-time claim is derived from an independent geometric construction (ε-block partition) and standard stochastic-localisation inequalities, with β_c defined by an explicit expectation unrelated to the mixing bound itself.

full rationale

The derivation chain begins with an explicit, non-circular definition of the temperature threshold β_c(d) via d·E[(tanh(γ β_c))^{2}]=1/4 (eq. 1.4). This value is chosen so that the aggregate squared influences Θ(u) concentrate below 1 (Thm 4.1), enabling the ε-weighting scheme (eqs. 4.6–4.7) that produces the ε-block partition (Def. 4.2). Existence and structural properties of the partition (trees/unicyclic components of controlled diameter, ε-block vertices on the boundary, short-cycle separation) are proved from first principles via Galton–Watson comparison, Chernoff bounds and a BFS exploration of G(n,d/n) (Thms 4.3, 15.2, 16.4 and supporting Lemmas 7.6, 17.1–19.2); none of these statements presupposes the mixing-time claim. Covariance-norm bounds on the multi-vertex blocks (Thm 9.1) are obtained by matrix-norm comparison on the all-paths trees of those blocks (Props 10.2, Claims 10.3–10.5), again using only the already-established geometric properties and the definition of the weights. Entropy decay along the localisation path follows from the standard Chen–Eldan / Liu–Mohanty–Rajaraman–Wu criterion (Thm 5.2) applied to the control matrices built from the good part of the partition (eqs. 5.9–5.10). The final mLSI lower bound (Thm 3.2) and mixing-time statement (Thm 1.1) are therefore ordinary consequences of these independent ingredients; no parameter is fitted to the target quantity, no uniqueness theorem is imported from the authors’ prior work to force the conclusion, and the only self-citations ([27] for a weaker path-coupling bound, [38] for the localisation template) supply non-load-bearing background. The argument is self-contained against external benchmarks.

Assumptions & free parameters 2 free parameters · 3 assumptions · 2 invented entities

The central claim rests on the existence of an ε-block partition (proved via concentration of Θ(u) and first-moment arguments on paths), on the Chen-Eldan / Liu et al. stochastic-localisation comparison theorem, and on standard random-graph facts (no dense small subgraphs). Free parameters ε, δ, ζ are chosen sufficiently small relative to d; they are not fitted to data but fixed once and for all to make the spectral and entropy inequalities close.

free parameters (2)
  • ε (block-partition parameter)
    Chosen in (0,1) small enough that 1-ε/8 ≥ κ=1/4; controls the weight threshold that separates light and heavy vertices.
  • δ, ζ (localisation shift parameters)
    Positive constants appearing in the shifted interaction matrix J and the control matrices C_t; taken sufficiently small so that the positive-definiteness and covariance bounds hold.
assumptions (3)
  • standard math Chen-Eldan stochastic-localisation comparison (Theorem 5.2 / [12,38]): mLSI of the original measure is at least the product of the terminal mLSI and the entropy-decay factor exp(-∫α_t dt).
    Invoked as a black-box functional inequality; the paper only verifies the spectral hypotheses of the theorem.
  • domain assumption Typical G(n,d/n) has no dense small subgraphs (Lemma 7.6) and maximum coupling O(√log n) (Lemma A.2).
    Standard first-moment / Chernoff facts used to guarantee that multi-vertex blocks remain trees or unicyclic of controlled size.
  • domain assumption The reconstruction threshold β_rec satisfies d E[(tanh(γ β_rec))^{2}]=1; the paper works at the stricter constant κ=1/4.
    Taken from the literature [26,36]; the factor-4 gap is an artefact of the localisation analysis rather than a new physical claim.
invented entities (2)
  • ε-block partition (Definition 4.2)
    purpose: Isolates high-degree / high-influence vertices inside small tree-like blocks so that the good part has spectral radius O(√d).
    Constructed from the aggregate squared influence Θ(u) and the path-weight M(P); existence proved by a multi-stage exploration algorithm.
  • Bespoke diagonal matrix D built from the recursive weights χ(u)=(1+δ)Γ χ(parent)
    purpose: Converts the operator-norm bound on Cov_B into an ∞-norm bound that can be controlled by the same path weights used for the block partition.
    Introduced solely for the covariance estimates of Theorems 9.1 and 10.1; no external verification.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On sampling diluted Spin-Glasses with unbounded interactions." pith.science (2026). https://pith.science/paper/4XGEM73V

@misc{pith2026260322432,
  author       = {Pith},
  title        = {Pith review of: On sampling diluted Spin-Glasses with unbounded interactions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4XGEM73V}},
  note         = {Machine review of arXiv:2603.22432}
}
abstract

Spin-glasses are natural Gibbs distributions that have been studied in Theoretical CS for many decades. Recently, they have been gaining attention from the community as they emerge naturally in neural computation and learning, network inference, optimisation and other areas. We study the problem of efficiently sampling from spin-glass distributions when the underlying graph is a typical instance of $G(n,d/n)$, i.e., the random graph on $n$ vertices such that each edge appears independently with probability $d/n$, and $d=\Theta(1)$. Our focus is on the 2-spin model at inverse temperature $\beta$. We consider this distribution to be one of the most interesting case of spin-glasses, and one of the most challenging to analyse, since its Gaussian couplings give rise to unbounded interaction. We employ the well-known Glauber dynamics to sample from the aforementioned distribution. We show that for the typical instances of the 2-spin model on $G(n,d/n)$, the mixing time of Glauber dynamics is $O\left(n^{1+\Theta(\frac{1}{\sqrt{d}})}\right)$, for any $\beta\leq \frac{1}{4\sqrt{d}}$. Our results can also be adapted for the case of spin-glass distributions with bounded interactions. In that respect, we obtain rapid mixing of Glauber dynamics for the Viana-Bray model on $G(n,d/n)$ when $\beta\leq \frac{1}{4\sqrt{d}}$. This improves on the current best bound which is $\beta<\frac{0.18}{\sqrt{d}}$. We utilise stochastic localisation, and in particular, we build and improve on the scheme introduced in [Liu, Mohanty, Rajaraman and Wu: FOCS 2024]. This is the first time that stochastic localisation is used for diluted spin-glasses, where both degrees and interactions can be unbounded.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 5 canonical work pages

  1. [1]

    Algorithmic barriers from phase transitions

    Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pages 793–802. IEEE Computer Society, 2008. URL:https://doi. org/10.1109/FOCS.2008.11

    doi:10.1109/focs.2008.11 2008

  2. [2]

    Algorithmic thresholds in mean field spin glasses.arXiv preprint arXiv:2009.11481, 2020

    Ahmed El Alaoui and Andrea Montanari. Algorithmic thresholds in mean field spin glasses.arXiv preprint arXiv:2009.11481, 2020

    arXiv 2009

  3. [3]

    Optimization of mean-field spin glasses.The Annals of Probability, 49(6):2922 – 2960, 2021

    Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Optimization of mean-field spin glasses.The Annals of Probability, 49(6):2922 – 2960, 2021. URL:https://doi.org/10.1214/21-AOP1519

    work page doi:10.1214/21-aop1519 2021

  4. [4]

    Trickle-down in localization schemes and applications

    Nima Anari, Frederic Koehler, and Thuy-Duong Vuong. Trickle-down in localization schemes and applications. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Comput- ing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1094–1105. ACM, 2024.doi:10.1145/3618260. 3649622

    doi:10.1145/3618260 2024

  5. [5]

    Spectral independence in high-dimensional expanders and applications to the hardcore model

    Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. In61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1319–1330. IEEE, 2020

    2020

  6. [6]

    Fast sampling via spectral independence beyond bounded-degree graphs

    Ivona Bez ´akov´a, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic. Fast sampling via spectral independence beyond bounded-degree graphs. In49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229, pages 21:1–21:16, 2022. 60

    2022

  7. [7]

    Modified logarithmic sobolev inequalities in discrete settings.Journal of Theoretical Probability, 19:289–336, 2006

    Sergey G Bobkov and Prasad Tetali. Modified logarithmic sobolev inequalities in discrete settings.Journal of Theoretical Probability, 19:289–336, 2006

    2006

  8. [8]

    Concentration inequalities

    St ´ephane Boucheron, G´abor Lugosi, and Olivier Bousquet. Concentration inequalities. InSummer school on machine learn- ing, pages 208–240. Springer, 2003

    2003

Show all 49 references
  1. [9]

    Path coupling: A technique for proving rapid mixing in markov chains

    Russ Bubley and Martin Dyer. Path coupling: A technique for proving rapid mixing in markov chains. InProceedings 38th Annual Symposium on Foundations of Computer Science, pages 223–231. IEEE, 1997

    1997

  2. [10]

    Approximate tensorization of entropy at high temperature

    Pietro Caputo, Georg Menz, and Prasad Tetali. Approximate tensorization of entropy at high temperature. InAnnales de la Facult´e des sciences de Toulouse: Math´ematiques, volume 24, pages 691–716, 2015

    2015

  3. [11]

    An almost constant lower bound of the isoperimetric coefficient in the kls conjecture.Geometric and Functional Analysis, 31:34–61, 2021

    Yuansi Chen. An almost constant lower bound of the isoperimetric coefficient in the kls conjecture.Geometric and Functional Analysis, 31:34–61, 2021

    2021

  4. [12]

    Localization schemes: A framework for proving mixing bounds for markov chains

    Yuansi Chen and Ronen Eldan. Localization schemes: A framework for proving mixing bounds for markov chains. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 110–122. IEEE, 2022

    2022

  5. [13]

    Rapid mixing of Glauber dynamics up to uniqueness via contraction

    Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mixing of Glauber dynamics up to uniqueness via contraction. In2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1307–1318. IEEE, 2020

    2020

  6. [14]

    Optimal mixing of glauber dynamics: entropy factorization via high- dimensional expansion

    Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of glauber dynamics: entropy factorization via high- dimensional expansion. InSTOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1537–1550. ACM, 2021

    2021

  7. [15]

    From algorithms to connectivity and back: Finding a giant component in randomk-sat

    Zongchen Chen, Nitya Mani, and Ankur Moitra. From algorithms to connectivity and back: Finding a giant component in randomk-sat. InProceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 3437–3470. SIAM, 2023. URL:https://doi.org/10.1137/1.978161197...

    2023 doi

  8. [16]

    On independent sets in random graphs

    Amin Coja-Oghlan and Charilaos Efthymiou. On independent sets in random graphs. InProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pages 136–144. SIAM, 2011. URL:https://doi. org/10.1137/1.9781611973082.12

    2011 doi

  9. [17]

    Charting the replica sym- metric phase.Communications in Mathematical Physics, 359:603–698, 2018

    Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, and Tobias Kapetanopoulos. Charting the replica sym- metric phase.Communications in Mathematical Physics, 359:603–698, 2018

    2018

  10. [18]

    Logarithmic sobolev inequalities for finite markov chains.The Annals of Applied Probability, 6(3):695–750, 1996

    Persi Diaconis and Laurent Saloff-Coste. Logarithmic sobolev inequalities for finite markov chains.The Annals of Applied Probability, 6(3):695–750, 1996

    1996

  11. [19]

    A new correlation inequality for ising models with external fields.Probability Theory and Related Fields, 186(1):477–492, 2023

    Jian Ding, Jian Song, and Rongfeng Sun. A new correlation inequality for ising models with external fields.Probability Theory and Related Fields, 186(1):477–492, 2023

    2023

  12. [20]

    Randomly coloring sparse random graphs with fewer colors than the maximum degree.Random Structures & Algorithms, 29(4):450–465, 2006

    Martin Dyer, Abraham D Flaxman, Alan M Frieze, and Eric Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree.Random Structures & Algorithms, 29(4):450–465, 2006

    2006

  13. [21]

    Dyer and Alan M

    Martin E. Dyer and Alan M. Frieze. Randomly coloring random graphs.Random Struct. Algorithms, 36(3):251–272, 2010. URL:https://doi.org/10.1002/rsa.20286

    2010 doi

  14. [22]

    MCMC sampling colourings and independent sets ofG(n, d/n) near uniqueness threshold

    Charilaos Efthymiou. MCMC sampling colourings and independent sets ofG(n, d/n) near uniqueness threshold. InProceed- ings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 305–316. SIAM, 2014

    2014

  15. [23]

    On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs

    Charilaos Efthymiou. On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs. In49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 ofLIPIcs, pages 57:1–57:16. Schloss Dagstuhl -...

    2022

  16. [24]

    On the mixing time of glauber dynamics for the hard-core and related models on g(n, d/n).CoRR, abs/2302.06172, 2023.arXiv:2302.06172,doi:10.48550/arXiv.2302.06172

    Charilaos Efthymiou and Weiming Feng. On the mixing time of glauber dynamics for the hard-core and related models on g(n, d/n).CoRR, abs/2302.06172, 2023.arXiv:2302.06172,doi:10.48550/arXiv.2302.06172

    2023 doi arXiv

  17. [25]

    Hayes, Daniel Stefankovic, and Eric Vigoda

    Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, and Eric Vigoda. Sampling random colorings of sparse ran- dom graphs. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1759–1...

    2018

  18. [26]

    Broadcasting with random matrices

    Charilaos Efthymiou and Kostas Zampetakis. Broadcasting with random matrices. In50th International Colloquium on Au- tomata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261, pages 55:1–55:14. Schloss Dagstuhl - Leibniz-Zentrum f ¨ur Inf...

    2023 doi

  19. [27]

    On sampling diluted spin-glasses using glauber dynamics

    Charilaos Efthymiou and Kostas Zampetakis. On sampling diluted spin-glasses using glauber dynamics. InThe Thirty Seventh Annual Conference on Learning Theory, pages 1501–1515. PMLR, 2024

    2024

  20. [28]

    Thin shell implies spectral gap up to polylog via a stochastic localization scheme.Geometric and Functional Analysis, 23(2):532–569, 2013

    Ronen Eldan. Thin shell implies spectral gap up to polylog via a stochastic localization scheme.Geometric and Functional Analysis, 23(2):532–569, 2013

    2013

  21. [29]

    A spectral condition for spectral gap: fast mixing in high-temperature ising models.Probability theory and related fields, 182(3-4):1035–1051, 2022

    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, 182(3-4):1035–1051, 2022

    2022

  22. [30]

    How well do local algorithms solve semidefinite programs? InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 604–614, 2017

    Zhou Fan and Andrea Montanari. How well do local algorithms solve semidefinite programs? InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 604–614, 2017

    2017

  23. [31]

    Exact solutions for diluted spin glasses and optimization problems.Physical review letters, 87(12):127209, 2001

    Silvio Franz, Michele Leone, Federico Ricci-Tersenghi, and Riccardo Zecchina. Exact solutions for diluted spin glasses and optimization problems.Physical review letters, 87(12):127209, 2001. 61

    2001

  24. [32]

    Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region.J

    Andreas Galanis, Daniel Stefankovic, and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region.J. ACM, 62(6):50:1–50:60, 2015

    2015

  25. [33]

    David Gamarnik, Aukosh Jagannath, and Alexander S. Wein. Low-degree hardness of random optimization problems. In61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 131–140. IEEE, 2020.doi:10.1109/FOCS46700.2020.00021

    2020 doi

  26. [34]

    Performance of sequential local algorithms for the random NAE-K-SAT problem.SIAM J

    David Gamarnik and Madhu Sudan. Performance of sequential local algorithms for the random NAE-K-SAT problem.SIAM J. Comput., 46(2):590–619, 2017

    2017

  27. [35]

    Modified logarithmic sobolev inequalities for some models of random walk.Stochastic processes and their applications, 114(1):51–79, 2004

    Sharad Goel. Modified logarithmic sobolev inequalities for some models of random walk.Stochastic processes and their applications, 114(1):51–79, 2004

    2004

  28. [36]

    The high temperature region of the Viana-Bray diluted spin glass model.Journal of statistical physics, 115:531–555, 2004

    Francesco Guerra and Fabio Lucio Toninelli. The high temperature region of the Viana-Bray diluted spin glass model.Journal of statistical physics, 115:531–555, 2004

    2004

  29. [37]

    Sampling approximately low-rank ising models: MCMC meets variational methods

    Frederic Koehler, Holden Lee, and Andrej Risteski. Sampling approximately low-rank ising models: MCMC meets variational methods. InConference on Learning Theory, 2022, volume 178 ofProceedings of Machine Learning Research, pages 4945–

    2022

  30. [38]

    Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, and David X. Wu. Fast mixing in sparse random ising models. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 120–128. IEEE, 2024.doi:10.1109/FOCS61266.2024.00018

    2024 doi

  31. [39]

    Lectures on glauber dynamics for discrete spin models.Lectures on probability theory and statistics (Saint- Flour, 1997), 1717:93–191, 1999

    Fabio Martinelli. Lectures on glauber dynamics for discrete spin models.Lectures on probability theory and statistics (Saint- Flour, 1997), 1717:93–191, 1999

    1997

  32. [40]

    M ´ezard, G

    M. M ´ezard, G. Parisi, and M. Virasoro.Spin glass theory and beyond. World Scientific, 1987

    1987

  33. [41]

    Gibbs rapidly samples colorings of g (n, d/n).Probability theory and related fields, 148(1- 2):37–69, 2010

    Elchanan Mossel and Allan Sly. Gibbs rapidly samples colorings of g (n, d/n).Probability theory and related fields, 148(1- 2):37–69, 2010

    2010

  34. [42]

    Exact thresholds for ising–gibbs samplers on general graphs.The Annals of Probability, 41(1):294–328, 2013

    Elchanan Mossel and Allan Sly. Exact thresholds for ising–gibbs samplers on general graphs.The Annals of Probability, 41(1):294–328, 2013

    2013

  35. [43]

    The parisi ultrametricity conjecture.Annals of Mathematics, pages 383–393, 2013

    Dmitry Panchenko. The parisi ultrametricity conjecture.Annals of Mathematics, pages 383–393, 2013

    2013

  36. [44]

    Infinite number of order parameters for spin-glasses.Physical Review Letters, 43(23):1754, 1979

    Giorgio Parisi. Infinite number of order parameters for spin-glasses.Physical Review Letters, 43(23):1754, 1979

    1979

  37. [45]

    Solvable model of a spin-glass.Physical review letters, 35(26):1792, 1975

    David Sherrington and Scott Kirkpatrick. Solvable model of a spin-glass.Physical review letters, 35(26):1792, 1975

    1975

  38. [46]

    The computational hardness of counting in two-spin models on d-regular graphs

    Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 361–369. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.56

    2012 doi

  39. [47]

    Princeton University Press, 2013

    Daniel L Stein and Charles M Newman.Spin glasses and complexity, volume 4. Princeton University Press, 2013

    2013

  40. [48]

    Non-backtracking spectra of weighted inhomogeneous random graphs.Mathemati- cal Statistics and Learning, 5(3):201–271, 2022

    Ludovic Stephan and Laurent Massouli ´e. Non-backtracking spectra of weighted inhomogeneous random graphs.Mathemati- cal Statistics and Learning, 5(3):201–271, 2022

    2022

  41. [49]

    The Parisi formula.Ann

    Michel Talagrand. The Parisi formula.Ann. Math. (2), 163(1):221–263, 2006.doi:10.4007/annals.2006.163.221. 62 APPENDIXA. SOMESTANDARDPROOFS A.1.Proof of Lemma 7.6.WriteE S for the event that every set of verticesS⊆V(G), with cardinality at most2 logn log2 d, spans at most|S|ed...

    2006 doi

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.