Pith. sign in

REVIEW 3 major objections 5 minor 35 references

Approximating the total variation distance between spin systems

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

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

Pith's one-line read This paper claims that total variation distance between two spin systems on the same graph can be approximated to relative error in polynomial time throughout the uniqueness regime, with an FPRAS running in \tilde{O}_\eta(\Delta…

desk verdict A serious algorithmic paper with a real sign error in the hardness reduction; the main TV-distance algorithms look solid but need the Poincare gap filled. read the letter →

arxiv 2502.05437 v2 pith:FLPKP4RK submitted 2025-02-08 cs.DS cs.LGmath.PR

Weiming Feng , Hongyang Liu , Minji Yang This is my paper · ORCID
classification cs.DScs.LGmath.PR MSC 68Q2568W2068Q1782B20
keywords totalvariationdistancespinsystemshardcoremodelIsingFPRASapproximatecountingsamplingoracle#P-hardness
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 asks whether the total variation distance between two Gibbs distributions on the same graph—say, two hardcore models or two Ising models—can be approximated with relative error in polynomial time even when the graph has unbounded treewidth. It answers positively in the uniqueness regime: the main algorithmic result is a randomized FPRAS running in \tilde{O}_\eta(\$\Delta$ $n^{7}$/\$varepsilon^{{5/2}}$) for two hardcore models whose activities stay below the uniqueness threshold with a constant gap \eta. The engine is a reduction from TV-distance estimation to sampling and approximate counting, plus a concentration argument built on the ratio variable W = w_\nu(\$\sigma$)/w_\mu(\$\sigma$). The paper also proves a boundary for marginal distributions: approximating the TV-distance between two single-vertex marginals is #P-hard even when both full distributions admit polynomial-time sampling and approximate counting, so relative-error approximation does not become easy merely because the individual distributions are tractable.

What carries the argument

The load-bearing object is the ratio variable W = w_\nu(\$\sigma$)/w_\mu(\$\sigma$) for \$\sigma$ \sim \mu, whose mean is Z_\nu/Z_\mu and whose deviation from its mean measures the TV distance via d_{\mathrm{TV}}(\mu,\nu) = \frac{Z_\mu}{2Z_\nu}\mathbb{E}[|W - \mathbb{E}[W]|]. The argument also relies on the parameter distance d_{\mathrm{par}}(\mu,\nu) between the two models' external fields, a Poincaré inequality on the marginal distribution over the big vertices, and a truncation lemma showing that the contribution of small-activity vertices is concentrated on constant-size independent sets. Together these pieces reduce relative-error TV estimation to sampling, approximate counting, and variance control.

What would settle it

Take a small hardcore graph with vertices of unequal activities all below \lambda_c(\$\Delta$), numerically compute the Poincaré constant or estimate the spectral gap of Glauber dynamics, and check whether Lemma 27's variance bound holds with a constant depending only on \eta; a counterexample would invalidate Lemma 24 and break Theorem 9.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that relative-error TV-distance estimation for spin systems is not inherently intractable. For two hardcore models on the same graph satisfying the uniqueness condition with a constant gap, there exists a fully polynomial randomized approximation scheme (FPRAS) with running time \tilde{O}_\eta(\$\Delta$ $n^{7}$/\$varepsilon^{{5/2}}$). The argument splits on the parameter distance between the two models: if the parameters differ enough, additive-error estimation suffices because the TV distance is already \$\Omega$(1/\mathrm{poly}(n)); if the parameters are close, a new estimator samples from the marginal on 'big' vertices, approximates contributions from 'small' vertices by truncating to constantly many occupied vertices, and controls variance with a Poincaré inequality. The companion hardness theorem shows that the analogous relative-error problem for a single-vertex marginal is #P-hard even inside the uniqueness regime, so the tractability of full-distribution TV distance does not extend to marginals.

Load-bearing premise

The entire uniqueness-regime algorithm rests on an unproven extension of a spectral-gap inequality to hardcore models with unequal vertex activities; if that extension fails, the variance bound in Lemma 24 and therefore the polynomial sample count in Theorem 9 collapse.

Editorial extensions

If this is right

  • If Theorem 9 is correct, hardcore TV-distance estimation is polynomial throughout the entire uniqueness regime, not just for product distributions or bounded-treewidth graphs.
  • Corollary 7 gives an FPRAS for Ising models satisfying the spectral condition, ferromagneticity with consistent fields, or antiferromagneticity within the uniqueness threshold, whenever the input models have a constant marginal lower bound.
  • Theorem 13 shows that additive-error approximation is easy: for hardcore models in the uniqueness regime, the TV distance between marginals on any subset S can be approximated in time \Delta n^2\varepsilon^{-4}\operatorname{polylog}(n/\varepsilon).
  • Theorem 11 and Corollary 12 imply that relative-error approximation of marginal TV distance is #P-hard for a single vertex and for almost-all-vertices subsets, even though sampling and approximate counting for the full distributions are polynomial-time.

Reading between the lines

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

  • One testable extension is to remove the marginal lower bound from Corollary 7 by applying the big-vertex/small-vertex decomposition used for hardcore models to the Ising case; the paper leaves this as an open problem.
  • The contrast between Theorem 9 and Theorem 11 suggests that the complexity of TV-distance estimation is governed not by whether the individual distributions can be sampled and counted, but by whether the conditioning structure needed for relative error can be localized.
  • The same ratio-variable reduction should extend to other spin systems, such as Potts models, whenever a Poincaré inequality or spectral gap is available for the relevant uniqueness regime.
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

3 major / 5 minor

Summary. The paper studies relative-error approximation of the total variation distance between two Gibbs distributions (hardcore or Ising) defined on the same graph. It gives a general reduction from TV-distance approximation to sampling and approximate counting (Theorem 5), with applications to hardcore models in the uniqueness regime, ferromagnetic Ising models, and Ising models satisfying a spectral condition. The headline algorithmic result is Theorem 9, an FPRAS for hardcore TV-distance in time \tilde{O}_\eta(\Delta n^7/\epsilon^{5/2}) under the uniqueness condition. The paper also gives an additive-error algorithm for marginal TV-distance (Theorem 13) and claims #P-hardness for relative-error approximation of single-vertex marginal TV-distance even when both models satisfy the uniqueness condition (Theorem 11, Corollary 12). The main technical engine is a variance-concentration argument for the likelihood-ratio estimator, combined with a partition of vertices into 'big' and 'small' activities and a tail-truncation argument for small independent sets.

Significance. If the proofs are completed, the algorithmic results would be a notable advance: they would provide the first polynomial-time relative-error TV-distance approximation for a broad class of graphical models beyond product distributions, and they give a clean reduction that leverages existing sampling and counting oracles. A particular strength is that the main algorithm is not parameter-fitted; the constants are derived analytically and the claims are stated with explicit running times. The hardness direction, aiming to show #P-hardness of marginal TV-distance even in a regime where sampling and counting are tractable, is an interesting and well-motivated complement to existing NP-hardness results for entire Gibbs distributions. However, as printed, the hardness proof contains a complement error in the marginal reduction, and two load-bearing technical points in the algorithmic proof (the Poincaré inequality for non-uniform hardcore models and the parameter verification in Lemma 25) are not established as written. These issues are all localized and likely repairable, but they currently block the central claims.

major comments (3)
  1. [Section 7 (Observation 42 and Algorithm 1)] The hardness reduction is built on the identity d_TV(\mu^{(i)}_i, \nu^\alpha_i)=|p_i-\alpha|, where p_i is defined in (50) as Pr[X_i=0 | X_1=\cdots=X_{i-1}=0]. In the hardcore encoding used throughout the paper, +1 means that the vertex is occupied in the independent set, so \mu^{(i)}_i(+1)=1-p_i. The correct identity is therefore d_TV(\mu^{(i)}_i,\nu^\alpha_i)=|1-p_i-\alpha|. Algorithm 1 starts at \alpha=1/2 and repeatedly moves \alpha toward the marginal probability of +1, so it converges to 1-p_i, not p_i; returning \hat{p}_i=\alpha does not satisfy the accuracy condition (51) needed for Proposition 40. The error is localized (returning 1-\alpha, or defining \nu^\alpha so that \nu^\alpha_i(-1)=\alpha, would repair it), but as printed Theorem 11 and Corollary 12 are not proved.
  2. [Appendix B (Lemma 27, Lemma 24, Theorem 23)] The Poincaré inequality for the marginal distribution \mu_B is asserted for hardcore models with non-uniform activities by saying that one can 'verify the technical condition in [CFYZ21, Theorem 1.9]', but no verification is supplied. The alternative argument via decay of \chi^2-divergence is only a pointer to another paper. This inequality is load-bearing: the variance bound V ar_{\mu_B}[h] \le O_\eta(d^2)(n^3+n/\kappa) in (33) is derived from it, and this bound is used in Lemma 24, Theorem 23, and ultimately Theorem 9. The manuscript must either prove the spectral-gap bound for non-uniform \lambda_v satisfying (1) or give a precise, checkable reduction to the cited result.
  3. [Section 5.2.2 (Lemma 31 and Lemma 25)] Equation (41) defines \eta(\kappa,t)=10^6(1+n/10)^{t+1}\kappa^t n^{t+2}, and the proof of Lemma 25 claims that with \kappa=10^{-9}\epsilon^{1/4}/n^{3/2} and t=4 this is at most \epsilon/200. With the printed definition, for t=4 one has \eta(\kappa,4)\approx 10^{-35}\epsilon n^5, which is not bounded by \epsilon/200 for arbitrary n. The proof of Lemma 31 actually derives a bound of the form (1+1/(10n))^{t+1}\kappa^t n^{t+2} times a constant, which is consistent with the desired tail bound; thus the statement of (41) appears to contain a typographical error in the factor (1+n/10). The statement and the parameter verification must be corrected, and the correction propagated through Lemma 25 and Theorem 23.
minor comments (5)
  1. [Section 4.2 heading] The heading 'total variance distance' should read 'total variation distance'.
  2. [Theorem 20 proof] In the sampling step, the text says 'Draw T samples \hat{Y}_1,\ldots,\hat{Y}_n'; the last index should be T, not n.
  3. [Theorem 20 proof] The opening line writes 'd_{TV}(\mu_S,\mu_S)' where the second argument should be \nu_S.
  4. [Claim 28] The displayed inequality '\mu^\sigma_v(+1)\ge \kappa/10 \ge 100nD\mu^\sigma_v(+1)+4D' is numerically false for the chosen constants (since \mu^\sigma_v(+1) can be as large as a constant, the right-hand side can be about 400n\theta, which exceeds \kappa/10). The subsequent variance bound does not appear to need this particular inequality, so the claim should be corrected or the unnecessary statement removed.
  5. [Section 3.2] In the proof of eq. (13), the lower bound is written as exp(p)|p-q|; the argument works only if p is the minimum of the two exponents. Since both exp(p) and exp(q) are at least b^2 by the marginal lower bound, the intended lower bound exp(min{p,q})|p-q| is valid, but the displayed expression is imprecise.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the TV-distance estimators are derived analytically from external sampling/counting oracles, and the hardness reduction starts from #Ind(3); cited self-work is independent background.

full rationale

The paper's derivation chain is self-contained against external oracles and known hardness results. The main algorithmic results (Theorems 5, 8, 9, 13) reduce TV-distance approximation to sampling and approximate counting oracles whose existence is cited from prior work ([CFYZ22, CE22, \u0160VV09] for hardcore; [AJK+22, FGW23, JS93] for Ising); the estimators and variance bounds are derived analytically rather than fitted, with constants such as C_TV^par = 1/5000, \theta, \kappa, and t chosen explicitly (Sections 3, 5.2, 6). The hardness proof (Theorem 11) starts from the external #P-complete problem #Ind(3) [DG00] and uses a Turing reduction via self-reducibility [JVV86], so it is not circular. The Poincar\'e inequality in Lemma 27 is cited from [CFYZ21], a prior published theorem by overlapping authors, but it is a mathematical tool with an independent proof, not an assumption that already contains the target TV-distance claim; Appendix B explicitly derives the marginal version from it. No step reduces by construction to its own input, and no fitted parameter is renamed as a prediction. The complement/sign issue in the Section 7 hardness reduction noted by the skeptic would be a correctness defect, not circularity, and does not affect this verdict.

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

The paper introduces no fitted numerical parameters and no new physical or mathematical entities. Its load-bearing inputs are prior sampling and counting oracles, the marginal lower bound condition, and an asserted extension of a Poincaré inequality.

assumptions (4)
  • domain assumption Sampling and approximate counting oracles with polynomial cost exist for hardcore models in the uniqueness regime (1) and for Ising models satisfying Condition 6.
    Invoked in Theorem 5 and Corollaries 7 through 9; sourced from prior work [CFYZ22, CE22, SVV09, AJK+22, FGW23, JS93, CCYZ24, JVV86]. If these oracles fail, the reductions have no substrate.
  • domain assumption Both input distributions are b-marginally bounded for a constant b (Condition 4).
    Required by the general algorithm (Theorem 5) and by Corollary 7. The paper states that removing it for Ising models is open.
  • ad hoc to paper The Poincaré inequality (spectral gap) holds for the hardcore marginal µ_B under the uniqueness condition with non-uniform activities.
    Appendix B asserts this follows from [CFYZ21, Theorem 1.9] by verification, but the verification is not given. This inequality is the basis of the variance bound Var[h] = O_eta(d^2)(n^3 + n/kappa) in Lemma 24.
  • domain assumption Hardcore uniqueness condition (1) and Ising Condition 6 characterize the regimes of interest.
    These are standard conditions from prior hardness and tractability results; the paper's theorems are stated relative to them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating the total variation distance between spin systems." pith.science (2026). https://pith.science/paper/FLPKP4RK

@misc{pith2026250205437,
  author       = {Pith},
  title        = {Pith review of: Approximating the total variation distance between spin systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FLPKP4RK}},
  note         = {Machine review of arXiv:2502.05437}
}
abstract

Spin systems form an important class of undirected graphical models. For two Gibbs distributions $\mu$ and $\nu$ induced by two spin systems on the same graph $G = (V, E)$, we study the problem of approximating the total variation distance $d_{TV}(\mu,\nu)$ with an $\epsilon$-relative error. We propose a new reduction that connects the problem of approximating the TV-distance to sampling and approximate counting. Our applications include the hardcore model and the antiferromagnetic Ising model in the uniqueness regime, the ferromagnetic Ising model, and the general Ising model satisfying the spectral condition. Additionally, we explore the computational complexity of approximating the total variation distance $d_{TV}(\mu_S,\nu_S)$ between two marginal distributions on an arbitrary subset $S \subseteq V$. We prove that this problem remains hard even when both $\mu$ and $\nu$ admit polynomial-time sampling and approximate counting algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 24 canonical work pages

  1. [1]

    Polynomial time and private learning of unbounded gaussian mixture models

    Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learning of unbounded gaussian mixture models. In ICML , volume 202 of Proceedings of Machine Learning Research , pages 1018--1040. PMLR , 2023

    work page 2023

  2. [2]

    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

  3. [3]

    Sharp bounds on aggregate expert error

    Ariel Avital and Aryeh Kontorovich. Sharp bounds on aggregate expert error. arXiv preprint arXiv:2407.16642 , 2024

    work page Pith review arXiv 2024

  4. [4]

    Meel, Dimitrios Myrisiotis, A

    Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinodchandran. On approximating total variation distance. In IJCAI , pages 3479--3487. ijcai.org, 2023

    work page 2023

  5. [5]

    Meel, Dimitrios Myrisiotis, A

    Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinodchandran. Total variation distance meets probabilistic inference. In ICML . OpenReview.net, 2024

    work page 2024

  6. [6]

    Meel, Dimitrios Myrisiotis, A

    Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinodchandran. Computational explorations of total variation distance. In ICLR . OpenReview.net, 2025

    work page 2025

  7. [7]

    Meel, and N

    Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, and N. V. Vinodchandran. Efficient distance approximation for structured high-dimensional distributions via learning. In NeurIPS , 2020

    work page 2020

  8. [8]

    Cl \' e ment L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Electron. Colloquium Comput. Complex. , TR15-063 , 2015

    work page 2015

Show all 35 references
  1. [9]

    Rapid mixing at the uniqueness threshold

    Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing at the uniqueness threshold. CoRR , abs/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 glauber dynamics via spectral independence for all degrees

    Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Rapid mixing of glauber dynamics via spectral independence for all degrees. In FOCS , pages 137--148. IEEE , 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]

    On the total variation distance of labelled markov chains

    Taolue Chen and Stefan Kiefer. On the total variation distance of labelled markov chains. In LICS , pages 33:1--33:10. ACM , 2014

    2014

  6. [14]

    Optimal mixing of G lauber dynamics: E ntropy factorization via high-dimensional expansion

    Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of G lauber dynamics: E ntropy factorization via high-dimensional expansion. In STOC , pages 1537--1550. ACM , 2021

    2021

  7. [15]

    L\( _ p \) distance and equivalence of probabilistic automata

    Corinna Cortes, Mehryar Mohri, and Ashish Rastogi. L\( _ p \) distance and equivalence of probabilistic automata. Int. J. Found. Comput. Sci. , 18(4):761--779, 2007

    2007

  8. [16]

    Canonne and Ronitt Rubinfeld

    Cl \' e ment L. Canonne and Ronitt Rubinfeld. Testing probability distributions underlying aggregated data. In ICALP , volume 8572 of Lecture Notes in Computer Science , pages 283--295. Springer, 2014

    2014

  9. [17]

    Dyer and Catherine S

    Martin E. Dyer and Catherine S. Greenhill. On markov chains for independent sets. J. Algorithms , 35(1):17--49, 2000

    2000

  10. [18]

    Henzinger, and Jean - Fran c ois Raskin

    Laurent Doyen, Thomas A. Henzinger, and Jean - Fran c ois Raskin. Equivalence of labeled markov chains. Int. J. Found. Comput. Sci. , 19(3):549--563, 2008

    2008

  11. [19]

    The total variation distance between high-dimensional gaussians with the same mean

    Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians with the same mean. arXiv preprint arXiv:1810.08693 , 2018

    2018 arXiv

  12. [20]

    A simple polynomial-time approximation algorithm for the total variation distance between two product distributions

    Weiming Feng, Heng Guo, Mark Jerrum, and Jiaheng Wang. A simple polynomial-time approximation algorithm for the total variation distance between two product distributions. TheoretiCS , 2, 2023

    2023

  13. [21]

    Swendsen- W ang dynamics for the ferromagnetic I sing model with external fields

    Weiming Feng, Heng Guo, and Jiaheng Wang. Swendsen- W ang dynamics for the ferromagnetic I sing model with external fields. Inf. Comput. , 294:105066, 2023

    2023

  14. [22]

    On deterministically approximating total variation distance

    Weiming Feng, Liqiang Liu, and Tianren Liu. On deterministically approximating total variation distance. In SODA , pages 1766--1791. SIAM , 2024

    2024

  15. [23]

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

    Andreas Galanis, Daniel Stefankovic, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic ising and hard-core models. Comb. Probab. Comput. , 25(4):500--559, 2016

    2016

  16. [24]

    Counting, sampling and integrating: algorithms and complexity

    Mark Jerrum. Counting, sampling and integrating: algorithms and complexity . Springer Science & Business Media, 2003

    2003

  17. [25]

    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

  18. [26]

    Valiant, and Vijay V

    Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. , 43:169--188, 1986

    1986

  19. [27]

    On computing the total variation distance of hidden markov models

    Stefan Kiefer. On computing the total variation distance of hidden markov models. In ICALP , volume 107 of LIPIcs , pages 130:1--130:13. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2018

    2018

  20. [28]

    e l Ouaknine, Bj \

    Stefan Kiefer, Andrzej S. Murawski, Jo \" e l Ouaknine, Bj \" o rn Wachter, and James Worrell. Language equivalence for probabilistic automata. In CAV , volume 6806, pages 526--540. Springer, 2011

    2011

  21. [29]

    On the tensorization of the variational distance

    Aryeh Kontorovich. On the tensorization of the variational distance. arXiv preprint arXiv:2409.10368 , 2024

    2024 arXiv

  22. [30]

    Probability and computing: randomization and probabilistic techniques in algorithms and data analysis

    Michael Mitzenmacher and Eli Upfal. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis . Cambridge university press, 2017

    2017

  23. [31]

    Computational transition at the uniqueness threshold

    Allan Sly. Computational transition at the uniqueness threshold. In FOCS , pages 287--296. IEEE Computer Society, 2010

    2010

  24. [32]

    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. In FOCS , pages 361--369. IEEE Computer Society, 2012

    2012

  25. [33]

    A complete problem for statistical zero knowledge

    Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. J. ACM , 50(2):196--249, 2003

    2003

  26. [34]

    Vempala, and Eric Vigoda

    Daniel S tefankovi c , Santosh S. Vempala, and Eric Vigoda. Adaptive simulated annealing: A near-optimal connection between sampling and counting. J. ACM , 56(3):18:1--18:36, 2009

    2009

  27. [35]

    Counting independent sets up to the tree threshold

    Dror Weitz. Counting independent sets up to the tree threshold. In STOC , pages 140--149. ACM , 2006

    2006

Pith tools

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