The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities

Ijay Narang; Will Perkins

REVIEW 1 major objections 5 minor 37 references

The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities

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

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

Pith's one-line read The paper proves that one spectral bound on the biadjacency matrix of a high-degree regular bipartite graph guarantees efficient approximate counting and sampling for the hard-core model at every fugacity.

desk verdict Genuinely new localization technique; the high-fugacity half hinges on a likely typo in the quoted Hadas–Peled condition that must be checked before the all-fugacity claim stands. read the letter →

arxiv 2608.03848 v1 pith:J35ZCWPP submitted 2026-08-04 cs.DS

Ijay Narang , Will Perkins This is my paper · ORCID

classification cs.DS

keywords hard-coremodelindependentsetsapproximatecountingsamplingGlauberdynamicsspectralexpansionbipartitegraphspolymermodels

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 proves that a purely spectral condition on a bipartite graph's biadjacency matrix—a small second singular value—certifies that the hard-core model (the distribution on independent sets weighted by λ^{|I|}) can be approximately counted and sampled at every fugacity λ>0, on high-degree regular graphs. At moderate λ it introduces tilted measures that penalize left-right occupation imbalance; their Glauber dynamics mix rapidly, and an exact discrete Gaussian identity reconstructs the original hard-core partition function as a positive mixture of the tilted ones. At high λ it shows that polymer-model phase dominance and cluster-expansion convergence follow from the same spectral bound, via a scale-sensitive Tanner inequality. If the theorem is right, this yields deterministic, efficiently checkable all-fugacity algorithms for a broad class of bipartite expanders and recovers earlier random-graph results as a special case. It matters because counting independent sets in bipartite graphs (#BIS) is a central open problem, and this identifies a broad regime where it becomes easy.

What carries the argument

The central object is the quadratically localized measure µ_{G,t,k}(I) ∝ t^{|I|} q^{f(m(I))+km(I)}, with q=1−Δ/n, f(a)=a²/2, and m(I)=|I∩L|−|I∩R|; a discrete Gaussian identity, Z_G(t)=Σ_k p_k Z_{G,k}(t) with p_k∝q^{k²/2}, expresses the hard-core partition function as an exact positive mixture. In the high-fugacity regime the load-bearing tools are the two-phase polymer models with weights λ^{|S|}/(1+λ)^{|N(S)|}, the scale-sensitive Tanner inequality |N(S)|/|S| ≥ Δ²/(σ²+(Δ²−σ²)|S|/n), and the Hadas–Peled long-range-order criterion.

What would settle it

Take a family of Δ-regular bipartite graphs whose second singular value meets the bound and set λ=1/(2σ2); if the single-site Glauber dynamics for the quadratically localized measure with k=0 mixes in time exponential in n, the moderate-regime half of the theorem is false. For the high-fugacity half, seek an independent set with more than n/Δ vertices on both sides whose weight exceeds the bound in Lemma 4.2 at the stated λ; such a set would falsify the long-range-order claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: there are absolute constants c>0 and Δ0 such that for every Δ≥Δ0, every Δ-regular bipartite graph with second singular value σ2(M_G)≤c(Δ²/log(eΔ))^{1/3} has an FPRAS for the hard-core partition function and an efficient approximate sampler at every fugacity λ>0. The proof establishes the moderate-fugacity range λ≤(1−ξ)/σ by showing that each quadratically localized measure has a controlled dependency matrix and hence rapidly mixing Glauber dynamics, and that the original partition function is an exact positive mixture of these localized partition functions. For the complementary high-fugacity range, it verifies the Hadas–Peled long-range-order criterion and

Load-bearing premise

The load-bearing premise is that the two external theorems it invokes—the rapid-mixing criterion for Glauber dynamics and the Hadas–Peled long-range-order theorem—apply without hidden restrictions to the tilted and polymer constructions used here; the paper checks their hypotheses but does not prove the theorems themselves.

Editorial extensions

If this is right

For every Δ-regular bipartite graph meeting the spectral bound, the hard-core partition function can be approximated to relative error ε and samples drawn to total-variation error ε in time polynomial in n and 1/ε, for every λ>0.
Uniformly random Δ-regular bipartite graphs satisfy the spectral condition for large Δ, so the all-fugacity algorithms apply with a certificate checkable on the given graph rather than only with high probability over the random construction.
The moderate-fugacity theorem gives FPRAS and efficient sampling for λ=O(1/σ) on every graph in the spectral class, matching the range previously known only for random regular bipartite graphs.
The high-fugacity theorem delivers FPTAS and efficient sampling for λ≥exp(C σ²/(Δ²−σ²) log(eΔ))−1, with cluster-expansion convergence following from the singular-spectrum bound alone.

Reading between the lines

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

Editorial inference: the quadratic-localization mechanism is not obviously specific to hard-core; the same 'cancel the rank-one direction' idea could plausibly extend to other two-spin antiferromagnetic models on bipartite expanders.
Editorial inference: the exponent 1/3 in the spectral threshold is likely not the true frontier; sharpening the high-fugacity overlap analysis may push the certificate toward σ=O(√Δ), matching Ramanujan graphs.
Editorial inference: because the certificate is a single singular value, it can be checked in near-linear time, making the theorem practically usable as a preprocessing test before running the algorithms.
Editorial inference: the paper does not address what happens outside the spectral bound; a natural test is whether the tilted-measure Glauber dynamics still mixes rapidly when σ is just above the stated threshold.

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.

Desk Editor's Note

read the letter

Let me get straight to it. This is a strong paper with one load-bearing thing to check before trusting it. The genuinely new part is discrete quadratic localization: tilt independent sets by q^{f(m)+km}, use a discrete Gaussian/Hubbard–Stratonovich identity to write Z_G(t) as an exact positive mixture over k, and show the tilted measures mix rapidly from a sigma_2 bound alone. That half is clean, self-contained, no fitted parameters. It gives an efficiently verifiable spectral certificate for moderate fugacity, which is a real improvement over what KOGT26 and JKP20 do for random graphs. The high-fugacity polymer argument follows the standard JKP20/CGSV22 template, but the novelty is deriving long-range order and the Kotecky–Preiss condition from sigma_2.

Now the soft spot. The stress-test note is correct on the printed text. The quoted Hadas–Peled condition (2.10) has second term (Delta/h)(|V|/r) M_LE. In Lemma 4.2, with r=|V|/(2Delta), |V|/r=2Delta, h>=Delta/4, M_LE=Delta, that term is up to 8Delta^2, not <=8. So if (2.10) is right, (4.9) proves the wrong inequality, and the high-fugacity threshold becomes exp(Omega(Delta)) — no overlap with the moderate range, and Theorem 1.1 falls. However, the paper's own bound in (4.9), namely <=8, is exactly what you get if the second term were (Delta/h)(|V|/r)/M_LE. So my guess is that (2.10) is a mistranscription of HP26, and the authors verified the correct condition. But as written, the proof applies a theorem it does not actually check. A referee has to pull HP26 and settle which form is right. This is not cosmetic; it is the load-bearing step. It also looks very fixable.

Other issues are minor. There is a sign typo in the same-side dependency display (q^{-1}-1 for q-1); the matrix right after uses the correct value. The reliance on CCC+25 and HP26 as black boxes is fine, since the hypotheses are clearly stated in the moderate-fugacity half, modulo the HP mismatch.

Bottom line: if the HP condition is what (4.9) verifies, this is a significant advance in the expander counting program. The paper deserves a serious referee; I would not desk reject. It needs a revision that quotes HP correctly and re-checks the constant chase. I would bring it to reading group — the localization idea alone is worth people seeing.

Referee Report

1 major / 5 minor

Summary. The paper studies approximate counting and sampling for the hard-core model on Δ-regular bipartite graphs under a spectral expansion condition. Let M_G be the biadjacency matrix and σ_2(M_G) its second singular value. The main result (Theorem 1.1) asserts that if σ_2(M_G) ≤ c(Δ²/log(eΔ))^{1/3}, then there is an FPRAS for the hard-core partition function and an efficient approximate sampler at every fugacity λ>0. The proof splits into two regimes. For moderate fugacity (Theorem 1.2), the authors introduce a family of quadratically tilted measures on the left-right imbalance, prove spectral independence for these tilted measures via the dependency-matrix criterion of [CCC+25], and use an exact discrete Hubbard–Stratonovich identity to express the hard-core model as a positive mixture of tilted measures. For high fugacity (Theorem 1.3), they refine the polymer-model approach: a Hadas–Peled long-range-order theorem gives phase dominance, and a Tanner-inequality-based verification of the Kotecký–Preiss condition gives convergent cluster expansions. The two fugacity ranges are matched to cover all λ>0.

Significance. If correct, the result is significant: it gives a single efficiently checkable spectral certificate for all-fugacity approximate counting and sampling on a natural class of bipartite expanders, recovering the previous random-regular-bipartite results and adding a certifying guarantee. The discrete quadratic localization technique is new and the mixture identity is exact and self-contained; there are no fitted parameters. The proof depends on two external black-box theorems ([CCC+25, Theorem 1.9] and [HP26, Theorem 1.7]); the manuscript verifies their hypotheses but does not prove the theorems themselves. I found no circularity or parameter fitting. The main caveat is a proof gap in the FPTAS guarantee at high fugacity, discussed below, which is repairable.

major comments (1)

[§4, Lemma 4.4 and proof of Theorem 1.3] The polymer-model approximation has an intrinsic bias: eZ_G(λ) := (1+λ)^n(Ξ_L+Ξ_R) satisfies eZ_G - Z_G = W_∩ - W_∅. Lemma 4.4 bounds (W_∩+W_∅)/Z_G by (2n+2) exp(-c n log(eΔ)/Δ²). For n = Θ(Δ²) and fixed Δ, this bound is a constant independent of n, not a quantity that can be made smaller than an arbitrarily small ε by running the algorithm longer. As written, the proposed FPTAS approximates eZ_G and does not control this bias to level ε for all ε. To obtain the stated FPTAS guarantee, the proof must add an exact enumeration branch when n is below an ε-dependent threshold (roughly n ≲ (Δ²/log Δ) log(1/ε)); for fixed Δ this is polynomial in 1/ε. The same issue affects the sampler's total-variation guarantee in Lemma 4.8. The claim is repairable, but the current text does not supply this step.

minor comments (5)

[§3.1, Lemma 3.1] In the proof of Lemma 3.1, after substituting √(r_L r_R) = t√q, the off-diagonal coefficient is -t q^{-1/2} E_S, not -t√q E_S. The displayed bound should read 2t q^{-1/2}|x^T E_S y| and tσ q^{-1/2}(||x||²+||y||²), not tσ√q. The consequence δ = 1 - tσ/√q is consistent with the corrected bound, so the error is local, but (3.6) as printed is not implied by the displayed algebra.
[§3.1, proof of Lemma 3.1] The prose states that for two available vertices on the same side Ψ_S(u,v) = q^{-1}-1. The correct value is q-1 = -a, which is what the matrix in (3.7) uses. Please fix the prose to match the matrix.
[§2.2 and §4.1, (2.10) and (4.9)] The expression rMLE should be typeset as a denominator, i.e. r M_LE, in both (2.10) and (4.9). If read as a product in the numerator, the bound (4.9) is off by a factor Δ²; with M_LE in the denominator it is exactly 8 under the paper's definitions. The ambiguity should be removed in the final version.
[§4] The proof of Theorem 1.3 assumes n ≥ Δ² (see Lemma 4.2). The theorem statement and Section 4 should explicitly state the enumeration case for n < Δ², and also the ε-dependent small-n case needed for the FPTAS guarantee discussed in the major comment.
[Theorem 1.3 statement] The fugacity threshold in (1.4) uses only σ²/(Δ²-σ²), while the proofs of Lemmas 4.2 and 4.9 use 1/Δ + σ²/(Δ²-σ²). This is harmless when n ≥ Δ² by Lemma 2.1, but the equivalence should be stated explicitly to avoid an apparent mismatch.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained given external black-box theorems; self-citations are not load-bearing.

full rationale

The moderate-fugacity proof (Section 3) is not circular. It introduces the quadratically localized measure (3.2), proves the exact mixture identity (3.8) via the discrete Gaussian Lemma 3.2, bounds the truncation error in Lemma 3.3, and verifies the spectral-independence hypothesis of the external criterion [CCC+25, Theorem 1.9] in Lemma 3.1. The spectral bound σ appears as an input hypothesis, not as an output, and no quantity is fitted to data. The high-fugacity proof (Section 4) invokes Hadas–Peled [HP26, Theorem 1.7] and the Kotecký–Preiss criterion as external black boxes and verifies their hypotheses (random-walk local expansion, Cheeger bound, Tanner inequality) from the spectrum; the polymer-algorithmic conversion follows [JKP20], a published independent result that does not assume the current spectral condition. Self-citations such as [NPWW26] and [GJM+26] are contextual or alternative proofs, not load-bearing. The identity (1.5) is an exact calculation, not a renamed input. A separate concern raised by the reviewer—that the bound in (4.9) may be off by a factor of Δ²—is a potential correctness/soundness gap in verifying the HP26 hypothesis, not a circularity, and does not raise the circularity score.

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

The paper introduces no fitted parameters and no ad hoc physical entities. The quadratically localized measures are algorithmic constructs, not free parameters. Its central results rest on standard spectral graph theory and on two external theorems ([CCC+25], [HP26]) cited as black boxes.

assumptions (5)

domain assumption Theorem 2.7 of [CCC+25]: a pinning-condition spectral independence bound implies an explicit Glauber dynamics mixing time.
Used to prove rapid mixing of the quadratically localized measures in Lemma 3.4; the theorem is taken as a black box from an unpublished preprint.
domain assumption Theorem 2.6 of [HP26]: the Hadas-Peled long-range-order criterion gives an exponential bound on independent sets with substantial occupation of both sides.
Used to establish phase dominance in the high-fugacity regime, Lemma 4.2; the theorem is taken as a black box from an unpublished preprint.
standard math Kotecký-Preiss cluster expansion convergence criterion (Theorem 2.8) and the algorithmic polymer framework of [JKP20] (Proposition 2.9).
Used to compute polymer partition functions and sample from polymer Gibbs distributions at high fugacity.
standard math Spectral graph theory facts: Cheeger inequality (Lemma 2.2) and the scale-sensitive Tanner inequality (Lemma 2.3) for bipartite graphs.
Used to convert the σ2 bound into edge and vertex expansion bounds, which feed the Hadas-Peled certificate and polymer verification.
standard math Connected-set counting bound: #{γ ∋ v : |γ| = t} ≤ (eΔ^2)^t, cited from [JKP20].
Used in the Kotecký-Preiss verification in Lemma 4.9.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities." pith.science (2026). https://pith.science/paper/J35ZCWPP

@misc{pith2026260803848,
  author       = {Pith},
  title        = {Pith review of: The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J35ZCWPP}},
  note         = {Machine review of arXiv:2608.03848}
}

abstract

We study approximate counting and sampling algorithms for the hard-core model on $\Delta$-regular bipartite graphs under a spectral expansion condition. Let $M_G$ be the biadjacency matrix of $G$. For every fixed $\xi\in(0,1)$, we give an FPRAS for the hard-core partition function and an efficient approximate sampler whenever \[ \lambda\leq \frac{1-\xi}{\sigma_2(M_G)}. \] The main idea is to introduce a family of quadratic tilts in the left-right occupation imbalance and show that each tilted measure can be sampled efficiently using Glauber dynamics. A discrete Gaussian identity expresses the original hard-core model as an exact positive mixture of these tilted measures; truncation and simulated annealing then yield efficient counting and sampling algorithms. For the complementary high-fugacity regime, we refine the polymer-model approach and show that the required phase-dominance and cluster expansion conditions follow from the singular-spectrum bound alone. Combining the two regimes, we obtain efficient approximate counting and sampling at every fugacity $\lambda>0$ whenever \[ \sigma_2(M_G)\leq c\left(\frac{\Delta^2}{\log(\mathrm e\Delta)}\right)^{1/3} \] for an absolute constant $c>0$. In particular, this recovers all-fugacity algorithms for random $\Delta$-regular bipartite graphs for all sufficiently large $\Delta$, while providing an efficiently verifiable certificate of their success on a given instance.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 35 canonical work pages

[1]

Entropic independence I : Modified log- S obolev inequalities for fractionally log-concave distributions and high-temperature I sing models

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

arXiv 2021
[2]

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

work page 2024
[3]

A very simple proof of the LSI for high temperature spin systems

Roland Bauerschmidt and Thierry Bodineau. A very simple proof of the LSI for high temperature spin systems. Journal of Functional Analysis , 276(8):2582--2588, 2019

work page 2019
[4]

Spectral gap in random bipartite biregular graphs and applications

Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris. Spectral gap in random bipartite biregular graphs and applications. Combinatorics, Probability and Computing , 31(2):229--267, 2022

work page 2022
[5]

Herm Jan Brascamp and Elliott H. Lieb. Some inequalities for gaussian measures and the long-range order of the one-dimensional plasma. In Michael Loss and Mary Beth Ruskai, editors, Inequalities: Selecta of Elliott H. Lieb , pages 403--416. Springer, Berlin, Heidelberg, 2002

work page 2002
[6]

Rapid mixing on random regular graphs beyond uniqueness, 2025

Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing on random regular graphs beyond uniqueness, 2025. arXiv:2504.03406v2

arXiv 2025
[7]

\# bis-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel S tefankovi c , and Eric Vigoda. \# bis-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences , 82(5):690--711, 2016

work page 2016
[8]

Sampling colorings and independent sets of random regular bipartite graphs in the non-uniqueness region

Zongchen Chen, Andreas Galanis, Daniel S tefankovi c , and Eric Vigoda. Sampling colorings and independent sets of random regular bipartite graphs in the non-uniqueness region. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2198--2207. SIAM, 2022

work page 2022

Show all 37 references

[9]

Pirogov-- S inai theory for the hard-core model beyond lattices

Sarah Cannon, Tyler Helmuth, and Will Perkins. Pirogov-- S inai theory for the hard-core model beyond lattices. Communications in Mathematical Physics , 407:129, 2026

2026
[10]

Fan R. K. Chung. Spectral Graph Theory , volume 92 of CBMS Regional Conference Series in Mathematics . American Mathematical Society, 1997

1997
[11]

The relative complexity of approximate counting problems

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica , 38(3):471--500, 2004

2004
[12]

An approximation trichotomy for boolean \#csp

Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. An approximation trichotomy for boolean \#csp . Journal of Computer and System Sciences , 76(3--4):267--277, 2010

2010
[13]

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

2022
[14]

A proof of Alon 's second eigenvalue conjecture

Joel Friedman. A proof of Alon 's second eigenvalue conjecture. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing , STOC '03, pages 720--724, New York, NY, USA, 2003. Association for Computing Machinery

2003
[15]

A simple proof of rapid mixing on random regular graphs beyond uniqueness

Andreas G \"o bel, Matthew Jenssen, Marcus Michelen, Marcus Pappik, Will Perkins, and Leon Schiller. A simple proof of rapid mixing on random regular graphs beyond uniqueness. arXiv preprint arXiv:2606.27545 , 2026

2026 arXiv
[16]

Inapproximability of the partition function for the antiferromagnetic I sing and hard-core models

Andreas Galanis, Daniel S tefankovi c , and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic I sing and hard-core models. Combinatorics, Probability and Computing , 25(4):500--559, 2016

2016
[17]

Expander graphs and their applications

Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society , 43(4):439--561, 2006

2006
[18]

On the critical fugacity of the hard-core model on regular bipartite graphs, 2026

Daniel Hadas and Ron Peled. On the critical fugacity of the hard-core model on regular bipartite graphs, 2026. arXiv:2603.27144

2026
[19]

Algorithmic pirogov--sinai theory

Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic pirogov--sinai theory. Probability Theory and Related Fields , 176(3--4):851--895, 2020

2020
[20]

Calculation of partition functions

John Hubbard. Calculation of partition functions. Physical Review Letters , 3(2):77--78, 1959

1959
[21]

Algorithms for \#bis -hard problems on expander graphs

Matthew Jenssen, Peter Keevash, and Will Perkins. Algorithms for \#bis -hard problems on expander graphs. SIAM Journal on Computing , 49(4):681--710, 2020

2020
[22]

A refined graph container lemma and applications to the hard-core model on bipartite expanders

Matthew Jenssen, Alexandru Malekshahian, and Jinyoung Park. A refined graph container lemma and applications to the hard-core model on bipartite expanders. Random Structures & Algorithms , 68(1):e70041, 2026

2026
[23]

Approximately counting independent sets in bipartite graphs via graph containers

Matthew Jenssen, Will Perkins, and Aditya Potukuchi. Approximately counting independent sets in bipartite graphs via graph containers. Random Structures & Algorithms , 63(1):215--241, 2023

2023
[24]

Umbrella sampling

Johannes K \"a stner. Umbrella sampling. WIREs Computational Molecular Science , 1(6):932--942, 2011

2011
[25]

Spectral gap for G lauber type dynamics for a special class of potentials

Yuri Kondratiev, Tobias Kuna, and Nataliya Ohlerich. Spectral gap for G lauber type dynamics for a special class of potentials. Electronic Journal Of Probability , 18, 2013

2013
[26]

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. In Proceedings of Thirty Fifth Conference on Learning Theory , volume 178 of Proceedings of Machine Learning Research , pages 4945--4988. PMLR, 2022

2022
[27]

Sampling from the hardcore model on random regular bipartite graphs above the uniqueness threshold

Nicholas Kocurek, Shayan Oveis Gharan, and Dante Tjowasi. Sampling from the hardcore model on random regular bipartite graphs above the uniqueness threshold. arXiv preprint arXiv:2604.21847 , 2026

2026 arXiv
[28]

Cluster expansion for abstract polymer models

Roman Koteck \'y and David Preiss. Cluster expansion for abstract polymer models. Communications in Mathematical Physics , 103(3):491--498, 1986

1986
[29]

Counting independent sets and colorings on random regular bipartite graphs

Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. Counting independent sets and colorings on random regular bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) , volume 145 of Leibniz International P...

2019
[30]

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 Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory , volume 134 of Proceedings of Machine Learning Research , pages...

2021
[31]

On the hardness of sampling independent sets beyond the tree threshold

Elchanan Mossel, Dror Weitz, and Nicholas Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields , 143(3--4):401--439, 2009

2009
[32]

Computational thresholds for balanced and fixed-slice independent sets in bipartite graphs

Ijay Narang, Will Perkins, Yuzhou Wang, and Timothy Wee. Computational thresholds for balanced and fixed-slice independent sets in bipartite graphs. arXiv preprint arXiv:2608.02503 , 2026

2026 arXiv
[33]

Computational transition at the uniqueness threshold

Allan Sly. Computational transition at the uniqueness threshold. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS) , pages 287--296. IEEE, 2010

2010
[34]

Counting in two-spin models on $d$-regular graphs

Allan Sly and Nike Sun. Counting in two-spin models on $d$-regular graphs. The Annals of Probability , 42(6):2383--2416, 2014

2014
[35]

Michael Tanner

R. Michael Tanner. Explicit concentrators from generalized N -gons. SIAM Journal on Algebraic Discrete Methods , 5(3):287--293, 1984

1984
[36]

G. M. Torrie and J. P. Valleau. Nonphysical sampling distributions in Monte Carlo free-energy estimation: Umbrella sampling. Journal of Computational Physics , 23(2):187--199, 1977

1977
[37]

Counting independent sets up to the tree threshold

Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages 140--149. ACM, 2006

2006

Pith tools

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

[1] [1]

Entropic independence I : Modified log- S obolev inequalities for fractionally log-concave distributions and high-temperature I sing models

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

arXiv 2021

[2] [2]

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

work page 2024

[3] [3]

A very simple proof of the LSI for high temperature spin systems

Roland Bauerschmidt and Thierry Bodineau. A very simple proof of the LSI for high temperature spin systems. Journal of Functional Analysis , 276(8):2582--2588, 2019

work page 2019

[4] [4]

Spectral gap in random bipartite biregular graphs and applications

Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris. Spectral gap in random bipartite biregular graphs and applications. Combinatorics, Probability and Computing , 31(2):229--267, 2022

work page 2022

[5] [5]

Herm Jan Brascamp and Elliott H. Lieb. Some inequalities for gaussian measures and the long-range order of the one-dimensional plasma. In Michael Loss and Mary Beth Ruskai, editors, Inequalities: Selecta of Elliott H. Lieb , pages 403--416. Springer, Berlin, Heidelberg, 2002

work page 2002

[6] [6]

Rapid mixing on random regular graphs beyond uniqueness, 2025

Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing on random regular graphs beyond uniqueness, 2025. arXiv:2504.03406v2

arXiv 2025

[7] [7]

\# bis-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel S tefankovi c , and Eric Vigoda. \# bis-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences , 82(5):690--711, 2016

work page 2016

[8] [8]

Sampling colorings and independent sets of random regular bipartite graphs in the non-uniqueness region

Zongchen Chen, Andreas Galanis, Daniel S tefankovi c , and Eric Vigoda. Sampling colorings and independent sets of random regular bipartite graphs in the non-uniqueness region. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2198--2207. SIAM, 2022

work page 2022