Pith. sign in

REVIEW 5 minor 1 cited by

Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs

T0 review · 0 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read This paper proves that conditioning the hard-core model on bipartite graphs to use both sides equally leaves the computational threshold unchanged, while fixing exact slice densities creates a hard region.

desk verdict Balanced hard-core threshold matches the unconstrained one; fixed-slice hardness is real. Main risk is imported Lemma 4.3, which deserves referee scrutiny. read the letter →

arxiv 2608.02503 v1 pith:RMXKHKH5 submitted 2026-08-03 cs.DS cs.CC

Ijay Narang , Will Perkins , Yuzhou Wang , Timothy L. H. Wee This is my paper · ORCID
classification cs.DScs.CC MSC 68Q2582B2060F0505C6968W20
keywords hard-coremodelbalancedindependentsetsfixedslicesapproximatecountingFPRASuniquenessthresholdphasecoexistencelocalCLT
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 studies two ways of constraining hard-core independent sets on bipartite graphs of maximum degree Δ: requiring equal occupation on the two sides, and fixing exact slice densities (αL, αR). It establishes a clean dichotomy for the balanced model: below the tree uniqueness threshold λ_c(Δ) there is an FPTAS and an efficient sampler, and above it there is neither unless NP=RP. This matches the known threshold for the unconstrained hard-core model on general bounded-degree graphs, meaning the balance constraint costs nothing at the level of computational phase transitions. For fixed slices, the paper proves a complementary hardness result: whenever the average density is between 1/Δ and 1/2 and the two side densities are more balanced than the phase-aligned ratios, approximate counting and sampling are NP-hard. The paper's significance is to map out which global constraints on bipartite independent sets are computationally benign and which are intrinsically hard.

What carries the argument

The algorithmic machinery is the tilted hard-core model with partition function Z_G(λ;t)=Σ λ^{|I|} e^{t B(I)}, where B(I)=|I∩L|−|I∩R|, and the balance-conditioned law is the tilted law conditioned on B(I)=0. Strong spatial mixing on the self-avoiding walk tree is proved through a two-level contraction in the coordinate x↦arcsinh(√x), uniform over compact tilts; a zero-freeness region for the complex tilted partition function then yields a local central limit theorem for B(I), so the acceptance probability of rejection sampling is Ω(n^{-1/2}). The hardness machinery is a phase-coexistence gadget obtained from a random Δ-regular bipartite graph by deleting matching edges and attaching (Δ−1)-ar

What would settle it

Compute the phase-restricted partition functions Z_{G,+} and Z_{G,-} on the exact tree-augmented gadget for moderate n and λ>λ_c(Δ); if their ratio is not n^{O(1)} or the terminal laws deviate from i.i.d. Bernoulli with parameters q_±=α_±/(1−α_∓) by more than n^{-2θ}, Lemma 4.3 fails. On the algorithmic side, run the tilted rejection sampler on random bipartite graphs with λ<λ_c(Δ) and check whether the empirical acceptance probability Pr_{μ_{λ,t}}(B(I)=0) is actually Θ(n^{-1/2}) across the tilt window used.

Watch

Extended reading notes

Core claim

The paper's central claim, Theorem 1.2, is that for every fixed Δ≥3 and every fugacity λ, the balanced hard-core model on bipartite graphs with equal side sizes has exactly the same algorithmic threshold as the ordinary hard-core model on bounded-degree graphs: tractable (FPTAS + efficient sampler) when λ<λ_c(Δ)=(Δ−1)^{Δ−1}/(Δ−2)^Δ, and intractable (no FPRAS, no efficient sampler) when λ>λ_c(Δ), unless NP=RP. The tractable side is proved by a tilted hard-core model with left/right fugacities λe^t and λe^{-t}, whose balance variable has a near-Gaussian distribution with variance Θ(n), giving a rejection-sampling acceptance probability Ω(1/√n); the hard side is proved by a phase-coexistence ga

Load-bearing premise

The hardness reductions rest on Lemma 4.3, imported without reproof, which asserts that in the non-uniqueness regime the random bipartite gadget has two well-separated phases with nearly independent terminal spins, partition functions within polynomial factors, and equal expected values; if these estimates fail for the exact tree-augmented gadget, the separation between balanced and unbalanced phase vectors collapses and the reductions to MIN-BISECTION and γ-MEBC break.

Editorial extensions

If this is right

  • If λ<λ_c(Δ), balance is computationally free: the balanced partition function and distribution on bipartite graphs with |L|≈|R| admit an FPTAS and an efficient sampler.
  • If λ>λ_c(Δ), the balanced problem is as hard as MIN-BISECTION: a polynomial-time e^{N^ζ}-factor approximation for a small ζ would yield a randomized algorithm for MIN-BISECTION, so no FPRAS or efficient sampler exists unless NP=RP.
  • Fixed slices with average density in (1/Δ, 1/2) and side densities more balanced than the phase-aligned ratios are hard in the worst case, so slice-based decompositions cannot by themselves give worst-case algorithms for #BIS.
  • Phase-aligned slices (ratios equal to α_−(λ)/α_+(λ) or its reciprocal) are not ruled out by the hardness result, and their tractability is left as an explicit open problem.

Reading between the lines

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

  • The boundary at the phase-aligned ratio may be a genuine computational phase transition: slices on the unbalanced side of that ratio might be tractable by an extension of the tilted-sampling argument, so one could test numerically whether fixed-slice sampling mixes rapidly exactly at the boundary.
  • The paper leaves λ=λ_c(Δ) open, conjecturing tractability via analogy with the unconstrained model; a numerical or rigorous check of whether the acceptance-probability bound persists at the critical fugacity would settle this gap.
  • The authors note that the phase-aligned-slice boundary in Theorem 1.1 may be an artifact of the proof rather than the true threshold; determining which slices are actually tractable would require new ideas and is a concrete next step.
  • The two-level contraction in arcsinh coordinates suggests the same tilting method could apply to other bipartite two-spin systems with a conserved difference, such as fixed-magnetization antiferromagnetic Ising models on bipartite graphs.
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 studies two conditional hard-core models on bipartite graphs of maximum degree Δ with equal side sizes: fixed-slice independent sets with prescribed densities (α_L, α_R), and balanced independent sets with |I∩L|=|I∩R|. Theorem 1.1 proves that for α=(α_L+α_R)/2 ∈ (1/Δ, 1/2) and side densities more balanced than the phase-aligned ratios, FixedSlice(α_L, α_R) has no FPRAS and no efficient sampling scheme unless NP=RP. Theorem 1.2 proves that the balanced model has the same computational threshold as the hard-core model on bounded-degree graphs: an FPTAS and efficient sampler below λ_c(Δ), and no FPRAS or efficient sampler above λ_c(Δ) unless NP=RP. The algorithmic side is based on a tilted hard-core model, strong spatial mixing on the SAW tree, zero-freeness, and a local central limit theorem; the hardness side uses random bipartite phase-coexistence gadgets and reductions from MIN-BISECTION and γ-MEBC.

Significance. If correct, these results give a clean worst-case threshold for the balanced hard-core model on bounded-degree bipartite graphs, matching the general hard-core threshold, and provide the first fixed-slice hardness results in the bipartite setting, showing that slice-decomposition does not by itself circumvent #BIS-hardness. The paper is unusually detailed: the two-level contraction proof for tilted SAW trees (Theorem 2.8), the zero-freeness result (Proposition 2.15), and the deterministic FPTAS in Section 3 are substantial technical contributions. The hardness framework is explicit, with careful terminal-compatibility calculations. The main caveat is that Lemma 4.3 imports pointwise phase estimates from [18,19] rather than reproving them in the exact tree-augmented gadget; this is a verification burden, not an internal inconsistency, and the manuscript states the specific transfer.

minor comments (5)
  1. [§4.1, Lemma 4.3] The hardness theorems rest on the imported pointwise estimates (3)–(8). The paper gives a proof sketch and cites [18, Proof of Lemma B.3] and [19, Lemmas 19/20/23, Section 7.2.1], but the reductions in §4.3 and §5 use the exact pointwise terminal-law ratio and the polynomial factor bounds. Since this is load-bearing, I recommend adding a short appendix or precise theorem statements reproducing the transfer to the tree-augmented gadget, or at least quoting the exact statements from [18,19]. This would remove the main verification burden without changing the results.
  2. [§2, Remark 2.2] The paper is transparent that the algorithm is proved only for bipartition ratios within a constant factor γ of balanced, and that unbalanced ratios are left open. This is not a defect for the stated theorem, but it would be helpful to note explicitly that Theorem 1.2 only claims equal side sizes, so the remark is simply an honest limitation of the stronger Proposition 2.1.
  3. [§1.2, Problem 1.4] The paper honestly notes that the fixed-slice hardness boundary may be an artifact of the proof and leaves the complementary region open. This is a useful pointer for future work, and the language is appropriately cautious.
  4. [§2.2, Proof of Theorem 2.8] Minor typos: 'abbreviated:= ∆−1' should be 'write d := ∆−1'; the notation λ†(u)(ζ) is used before being defined; and the heading 'Proof of Proposition 2.9.' appears twice. These should be cleaned up before publication.
  5. [§2.4, Proposition 2.15] In the proof of Proposition 2.15, the case δ ≥ λ_c(Δ) is dismissed as making the interval for λ empty. More precisely, the condition λ ∈ (0, λ_c−δ) is empty, so this is fine, but the sentence could be clarified to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: thresholds, gadget estimates, and reductions are all anchored in external or independently proved results.

full rationale

The central claims are not circular. The algorithmic threshold is fixed by the tree uniqueness value λ_c(Δ) and the balanced model is defined directly as the hard-core model conditioned on |I∩L|=|I∩R|; the FPTAS and sampler are obtained from self-contained SAW-tree contraction, zero-freeness, and local CLT arguments. The local CLT proof borrows strategies and lemmas from [24] (Jain–Perkins–Sah–Sawhney), which is a prior published result about univariate hard-core local limit theorems; its assumptions do not include the balanced or tilted model of this paper, so it is independent support rather than a self-referential premise. The hardness side rests on Lemma 4.3, whose terminal-law and phase-slice estimates are imported from [18,19] (Galanis–Štefankovič–Vigoda), not from the present authors' prior work and not assuming the current conclusions. This is a legitimate inheritance of gadget analysis, though it is a genuine correctness risk if those estimates do not transfer to the exact growing-terminal gadget; risk is not circularity. The reductions from MIN-BISECTION and γ-MEBC compute the inter-gadget compatibility factor explicitly from the product terminal law Q_T^Y, with the phase ratio α_-/α_+ and fugacity λ(α) derived from the tree, not fitted to the target. No equation in the paper reduces by construction to its own input, and no fitted parameter is renamed as a prediction.

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

The proofs use construction constants (theta, psi, gamma, u, lambda*) chosen to satisfy inequalities, but no constants are fitted to computational experiments or data. The central claims rest on standard threshold theorems, the imported gadget estimates of [18, 19], and standard facts used as axioms above. No new physical or algorithmic entity with independent falsifiable evidence is introduced.

free parameters (4)
  • theta, psi gadget degree parameters = unspecified constants in (0,1/8), theta+psi<1/4
    Chosen to make h = Theta(n^{theta/4}), k = floor(n^{3theta/4}), kh^2 = o(n/h), and n^theta = o(n/h^2). Any sufficiently small pair works; the theorem does not depend on their numerical values.
  • gamma fixed-slice phase fraction = gamma = (1/2)(1 + delta(1+u)/d) in (0,1) cap Q
    Chosen to center the target fixed slice on phase vectors with j0 = gamma h plus-gadgets. A construction parameter derived from the target densities, not fitted to data.
  • lambda* working fugacity in fixed-slice proof = lambda* in (lambda_c(Delta), lambda_0) close to lambda_0
    Chosen so that p = lambda*/(1+lambda*) > alpha and (a_+ + a_-)/2 < alpha, enabling equation (5.1). Existence is argued from continuity; no numerical fitting.
  • u isolated-vertex ratio = u = (alpha - (a_+ + a_-)/2)/(p - alpha) > 0
    Defined to make the target slice align with phase vector D(Y) = D0. It is a closed-form construction choice, not a fitted constant.
assumptions (5)
  • domain assumption Known hard-core threshold theorems: lambda < lambda_c(Delta) gives FPTAS/efficient sampling via Weitz's SAW tree; lambda > lambda_c(Delta) gives no FPRAS/efficient sampling unless NP=RP (Sly, Sly-Sun, Galanis et al.).
    Used as the benchmark threshold in Theorem 1.2 and to set the phase regime of the gadgets. Invoked in Sections 1, 2, and 4.
  • domain assumption Lemma 4.3 single-gadget estimates: phase-restricted terminal laws are nearly i.i.d. product measures with probabilities q_+, q_-; phase partition functions are within polynomial factors; E Z_{G,+} = E Z_{G,-}; ratio Z_{G,+}/Z_{G,-} is polynomial.
    Imported from [18, 19]. The inter-gadget compatibility factor and the balance/cut encoding both rely on these estimates. The paper does not re-prove them.
  • standard math Fact 4.1: MIN-BISECTION is NP-hard; Fact 5.1: gamma-MEBC is NP-hard for rational gamma in (0,1).
    Source problems for the two hardness reductions. Standard known results from [20] and [16].
  • standard math Weitz's self-avoiding walk tree identity for hard-core occupation ratios, and the Michelen-Sahasrabudhe CLT-to-zero-free-region theorem (Theorem 2.20).
    Used for the marginal oracle in Algorithms 2-3 and for the low-frequency characteristic-function bounds in the local CLT proof. External theorems relied on without proof.
  • domain assumption For lambda > lambda_c(Delta), the hard-core model on the infinite Delta-regular tree has two distinct semi-translation-invariant Gibbs states with root occupation probabilities alpha_+(lambda) > alpha_-(lambda).
    The whole phase-coexistence gadget construction assumes this separation and the tree-phase interpretation of alpha_+, alpha_-. Used throughout Section 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs." pith.science (2026). https://pith.science/paper/RMXKHKH5

@misc{pith2026260802503,
  author       = {Pith},
  title        = {Pith review of: Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RMXKHKH5}},
  note         = {Machine review of arXiv:2608.02503}
}
abstract

Motivated by recent work of Kocurek, Oveis Gharan, and Tjowasi, which gives an efficient sampling algorithm for the hard-core model on random regular bipartite graphs by decomposing into fixed-size slices, we study the worst-case tractability of approximate counting and sampling of fixed-size slices for bipartite independent set problems. Let $G=(L\sqcup R,E)$ be a bipartite graph with $|L|=|R|=n$ and maximum degree $\Delta$. The fixed-slice problem asks to sample uniformly from independent sets satisfying $|I\cap L|=\alpha_L n$ and $|I\cap R|=\alpha_R n$. We show that if the overall density $\alpha$ lies in the interval $(\frac{1}{\Delta}, \tfrac{1}{2})$, and the densities on the two sides are more balanced than the typical phase densities of a random $\Delta$-regular bipartite graph, then there is no FPRAS or efficient sampling scheme unless $\mathbf{NP}=\mathbf{RP}$. We then study a related fugacity model in which the densities are not fixed, but the independent set is required to be balanced between the two sides of the bipartition. For $\lambda>0$, the balanced hard-core model is the ordinary hard-core model with fugacity $\lambda$, conditioned on the event $|I\cap L|=|I\cap R|$. We prove that this model has the same computational threshold as the hard-core model on general bounded-degree graphs. That is, for every fixed $\Delta\ge 3$, if $\lambda<\lambda_c(\Delta)$, then the balanced partition function admits an FPTAS and the balanced hard-core distribution admits an efficient sampling scheme. Conversely, if $\lambda>\lambda_c(\Delta)$, then no FPRAS or efficient sampler exists on this graph class unless $\mathbf{NP}=\mathbf{RP}$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    cs.DS 2026-08 conditional novelty 8.0 of 10

    A bound on the second biadjacency singular value alone certifies FPRAS counting and polynomial-time sampling for the hard-core model at every fugacity on Δ-regular bipartite graphs.

Reference graph

Works this paper leans on

38 extracted references · 3 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Springer, 2016

    Alexander Barvinok.Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and Combinatorics. Springer, 2016

    2016

  2. [2]

    A quantitative local limit theorem for triangles in random graphs, 2016

    Ross Berkowitz. A quantitative local limit theorem for triangles in random graphs, 2016. arXiv preprint arXiv:1610.01281

    arXiv 2016

  3. [3]

    # 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

    Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, 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

    2016

  4. [4]

    Pirogov–Sinai theory for the hard-core model beyond lattices.Communications in Mathematical Physics, 407:129, 2026

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

    2026

  5. [5]

    Counting independent sets in unbalanced bipartite graphs

    Sarah Cannon and Will Perkins. Counting independent sets in unbalanced bipartite graphs. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1456–1466. SIAM, 2020

    2020

  6. [6]

    Computational thresholds for the fixed-magnetization ising model

    Charlie Carlson, Ewan Davies, Alexandra Kolla, and Will Perkins. Computational thresholds for the fixed-magnetization ising model. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1459–1472. ACM, 2022

    2022

  7. [7]

    Rapid mixing at the uniqueness threshold

    Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing at the uniqueness threshold. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 879–890, 2025

    2025

  8. [8]

    Uniqueness and rapid mixing in the bipartite hardcore model (extended abstract)

    Xiaoyu Chen, Jingcheng Liu, and Yitong Yin. Uniqueness and rapid mixing in the bipartite hardcore model (extended abstract). In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1991–2005. IEEE, 2023

    1991

Show all 38 references
  1. [9]

    Zero-freeness of the hard-core model with bounded connective constant, 2026

    Yuan Chen, Shuai Shao, and Ke Shi. Zero-freeness of the hard-core model with bounded connective constant, 2026. arXiv preprint arXiv:2604.02746

    2026 arXiv

  2. [10]

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

    Zongchen Chen, Andreas Galanis, Daniel Štefankovič, 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

    2022

  3. [11]

    Approximately counting independent sets of a given size in bounded-degree graphs.SIAM Journal on Computing, 52(2):618–640, 2023

    Ewan Davies and Will Perkins. Approximately counting independent sets of a given size in bounded-degree graphs.SIAM Journal on Computing, 52(2):618–640, 2023

    2023

  4. [12]

    R. L. Dobrushin and Brunello Tirozzi. The central limit theorem and the problem of equivalence of ensembles.Communications in Mathematical Physics, 54(2):173–192, 1977

    1977

  5. [13]

    The relative complexity of approximate counting problems.Algorithmica, 38(3):471–500, 2004

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

    2004

  6. [14]

    An approximation trichotomy for boolean #csp.Journal of Computer and System Sciences, 76(3–4):267–277, 2010

    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

  7. [15]

    Relations between average case complexity and approximation complexity

    Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 534–543. ACM, 2002

    2002

  8. [16]

    On cutting a few vertices from a graph

    Uriel Feige, Robert Krauthgamer, and Kobbi Nissim. On cutting a few vertices from a graph. Discrete Applied Mathematics, 127(3):643–649, 2003

    2003

  9. [17]

    Improved inapprox- imability results for counting independent sets in the hard-core model.Random Structures & Algorithms, 45(1):78–110, 2014

    Andreas Galanis, Qi Ge, Daniel Štefankovič, Eric Vigoda, and Linji Yang. Improved inapprox- imability results for counting independent sets in the hard-core model.Random Structures & Algorithms, 45(1):78–110, 2014

    2014

  10. [18]

    Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region.Journal of the ACM, 62(6):50:1–50:60, 2015

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

    2015

  11. [19]

    Inapproximability of the partition function for the antiferromagnetic ising and hard-core models.Combinatorics, Probability and Computing, 25(4):500–559, 2016

    Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic ising and hard-core models.Combinatorics, Probability and Computing, 25(4):500–559, 2016

    2016

  12. [20]

    Some simplified np-complete problems

    Michael R Garey, David S Johnson, and Larry Stockmeyer. Some simplified np-complete problems. InProceedings of the sixth annual ACM symposium on Theory of computing, pages 47–63. ACM, 1974

    1974

  13. [21]

    Walter de Gruyter, 2011

    Hans-Otto Georgii.Gibbs measures and phase transitions, volume 9. Walter de Gruyter, 2011

    2011

  14. [22]

    Algorithmic Pirogov–Sinai theory.Probability Theory and Related Fields, 176(3–4):851–895, 2020

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

    2020

  15. [23]

    Optimal mixing of the down-up walk on independent sets of a given size

    Vishesh Jain, Marcus Michelen, Huy Tuan Pham, and Thuy-Duong Vuong. Optimal mixing of the down-up walk on independent sets of a given size. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1665–1681. IEEE, 2023

    2023

  16. [24]

    Approximate counting and sampling via local central limit theorems

    Vishesh Jain, Will Perkins, Ashwin Sah, and Mehtaab Sawhney. Approximate counting and sampling via local central limit theorems. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1473–1486. ACM, 2022

    2022

  17. [25]

    Algorithms for #BIS-hard problems on expander graphs.SIAM Journal on Computing, 49(4):681–710, 2020

    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

  18. [26]

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

    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

  19. [27]

    Approximately counting independent sets in bipartite graphs via graph containers.Random Structures & Algorithms, 63(1):215–241, 2023

    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

  20. [28]

    Sampling from the hardcore model on random regular bipartite graphs above the uniqueness threshold.arXiv preprint arXiv:2604.21847, 2026

    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. 62

    2026 arXiv

  21. [29]

    Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs.Random Structures & Algorithms, 67(4):e70038, 2025

    Aiya Kuchukova, Marcus Pappik, Will Perkins, and Corrine Yap. Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs.Random Structures & Algorithms, 67(4):e70038, 2025

    2025

  22. [30]

    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. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 ofLeibniz International Proc...

    2019

  23. [31]

    Fptas for #BIS with degree bounds on one side

    Jingcheng Liu and Pinyan Lu. Fptas for #BIS with degree bounds on one side. InProceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 549–556. ACM, 2015

    2015

  24. [32]

    Central limit theorems and the geometry of polynomials.Journal of the European Mathematical Society, 28(5):2261–2305, 2026

    Marcus Michelen and Julian Sahasrabudhe. Central limit theorems and the geometry of polynomials.Journal of the European Mathematical Society, 28(5):2261–2305, 2026

    2026

  25. [33]

    Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials.SIAM Journal on Computing, 46(6):1893–1919, 2017

    Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials.SIAM Journal on Computing, 46(6):1893–1919, 2017

    1919

  26. [34]

    On the hardness of finding balanced independent sets in random bipartite graphs

    Will Perkins and Yuzhou Wang. On the hardness of finding balanced independent sets in random bipartite graphs. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2376–2397. SIAM, 2024

    2024

  27. [35]

    Spatial mixing and the connective constant: Optimal bounds.Probability Theory and Related Fields, 168(1–2):153–197, 2017

    Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič, and Yitong Yin. Spatial mixing and the connective constant: Optimal bounds.Probability Theory and Related Fields, 168(1–2):153–197, 2017

    2017

  28. [36]

    Computational transition at the uniqueness threshold

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

    2010

  29. [37]

    Counting in two-spin models ond-regular graphs.The Annals of Probability, 42(6):2383–2416, 2014

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

    2014

  30. [38]

    Counting independent sets up to the tree threshold

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

    2006

Pith tools

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