Pith. sign in

REVIEW 6 minor 289 references

A Counting Lov\'asz Local Lemma

T0 review · 0 major / 6 minor · reviewed 2026-08-14 · 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 a counting analogue of the local lemma: under $4ep(D+1)^2\le1$, the number of satisfying assignments of any CSP can be approximated in polynomial time, matching the $pD^2$ hardness threshold up to constant factors.

desk verdict The paper delivers the pD^2-scale counting LLL for general CSPs, and the reader's main objection is resolved by the per-constraint independent sampling in Algorithm 2. read the letter →

arxiv 2608.08616 v1 pith:EZQM5NLQ submitted 2026-08-09 cs.DS cs.DMmath.PR

Hongyang Liu , Chunyang Wang , Yitong Yin , Yiyao Zhang , Can Zhou This is my paper · ORCID
classification cs.DScs.DMmath.PR
keywords approximatecountinglocallemmaconstraintsatisfactionproblems2-treeexpansioncorrelationdecaymarginalsrandomizedestimationpolynomial-timealgorithm
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 establishes a counting analogue of the local lemma: for any constraint satisfaction problem in which each constraint is violated with probability at most $p$ and shares variables with at most $D$ others, the number of satisfying assignments can be approximated in polynomial time whenever $4e\,p\,(D+1)^2\le1$. This is the $pD^2$ scale that prior hardness results showed is necessary for counting, so the tractable threshold is now determined up to constant factors. The proof works by expanding each constraint's marginal violation probability over 2-trees---sets of constraints that are independent in the dependency graph but connected at distance two---and showing the expansion decays exponentially at exactly this scale. From that expansion the paper derives a deterministic estimator and a randomized one, the latter running in $\mathrm{poly}(k,D,q)\,(n/\varepsilon)^2$ time with success probability $3/4$, where $k$ is the maximum constraint width and $q$ the maximum domain size.

What carries the argument

A 2-tree is a set of constraints that is independent in the dependency graph (no two share a variable) yet connected in the square graph (constraints linked through a common neighbor). The load-bearing object is the canonical 2-tree expansion: the algorithm assigns every subset of constraints a canonical 2-tree by a greedy scan, then groups the inclusion-exclusion terms for a marginal according to that tree. The 'free' constraints of a tree are the constraints whose presence does not change the canonical tree, and the inverse image of a tree is exactly the tree plus any subset of those free constraints; summing signs over free subsets reduces the inner sum to one event probability. The expansion carries the correlation-decay analysis: the difference between two evaluations of the recursion is bounded by a weighted sum over rooted 2-trees, with weight $(1.2\beta)^{|T|}$ per tree and at most $(eD^2)^{|T|-1}$ trees of a given size, so the $pD^2$ condition makes the whole sum exponentially small.

What would settle it

A concrete weak point is testable: in a CSP satisfying $4e\,p\,(D+1)^2\le1$, insert two identical constraints over the same variables so their violation events coincide; if one rooted 2-tree contains the first copy and another rooted 2-tree contains the second, the union's violation probability is $p$, not $p^{|T\cup T'|}$. If the empirical second moment of the randomized marginal estimator on this instance exceeds $40p$, or its expected recursive cost grows beyond $\mathrm{poly}(k,D,q)$, then the variance and runtime claims fail. A direct check is to compute the off-diagonal term in the paper's Lemma 5.6 for this instance and see whether it stays below $24p$.

Watch

Extended reading notes

Core claim

On its own terms, the central discovery is a recursive identity for the marginal probability $r_{C,c_0}$ that one constraint is violated given that all others are satisfied: the inclusion-exclusion sum over subsets of constraints is regrouped by the canonical 2-tree each subset generates, and for every 2-tree the preimage turns out to be exactly the tree plus any subcollection of its free constraints. That collapses the inner sum to one joint probability, leaving $r_{C,c_0}$ as a signed sum over rooted 2-trees with reciprocal factors for smaller instances. Each tree of size $t$ contributes at most about $p^t$, and the number of such trees is at most $(eD^2)^{t-1}$, so the series is dominated by small trees precisely when $4e p(D+1)^2 \le 1$. The paper then proves two estimators satisfy the advertised bounds: truncating the recursion at depth $L$ gives a deterministic estimate with error at most $4(0.9)^L$, while randomizing the recursion---activating each tree with probability equal to its joint violation probability and estimating the reciprocal factors with an unbiased estimator---gives a random variable with mean $r_{C,c_0}$ and second moment at most $40p$. Telescoping these marginals over an ordering of the constraints yields the multiplicative approximation of the partition function.

Load-bearing premise

The result rests on the premise that the probability of all constraints in the union of any two rooted 2-trees being violated is at most $p^{|T\cup T'|}$; when constraints are repeated or share variables, violation events can be positively correlated, so the variance and expected-runtime bounds for the randomized estimator would no longer be guaranteed.

Editorial extensions

If this is right

  • Under $4ep(D+1)^2\le1$, the number of satisfying assignments of any CSP, in the evaluation-oracle model, can be approximated to relative error $\varepsilon$ in $\mathrm{poly}(k,D,q)\,(n/\varepsilon)^2$ randomized time.
  • The same condition supports a deterministic algorithm with cost $(nD/\varepsilon)^{O(kD\log q)}$, giving a worst-case guarantee without randomness.
  • For general CSPs the counting condition improves from $pD^5\lesssim1$ to $pD^2\lesssim1$; for $k$-SAT the improvement is from $pD^{4.82}\lesssim1$ to the same $pD^2$ scale.
  • Because the marginal recursion preserves the local lemma condition in every recursive subinstance, the method applies not only to whole formulas but to any sub-CSP obtained by deleting constraints, which is what makes the telescoping product over constraints valid.
  • Since hardness results forbid counting beyond constant factors at $pD^2$, any further improvement in the constant or the exponent would require breaking those lower bounds or a fundamentally different algorithmic idea.

Reading between the lines

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

  • The alternating signs in the recursion mean the estimator is not a probability distribution, so converting counting into sampling under the same $pD^2$ condition would need a separate mechanism, such as a signed cluster expansion or partial rejection sampling; the paper leaves this open.
  • Because the expansion is organized around distance-two connectivity rather than connected clusters, it may extend to lopsided or abstract local lemma settings where the dependency structure is a general graph rather than variable overlap.
  • For random $k$-SAT just below the satisfiability threshold, the $pD^2$ condition translates into a constraint-density bound, so applying the randomized estimator there gives an empirical check of whether expected runtime stays small outside worst-case instances.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 6 minor

Summary. The paper establishes a counting analogue of the Lovász Local Lemma for general constraint satisfaction problems. Under the condition 4e·p·(D+1)^2 ≤ 1, where p is the maximum constraint violation probability and D is the maximum dependency degree, it gives two approximate counting algorithms: a deterministic algorithm with cost (nD/ε)^{O(kD log q)} and a randomized algorithm with expected cost poly(k,D,q)·(n/ε)^2. The core technical contribution is a 2-tree expansion of constraint marginal violation probabilities, obtained by regrouping the inclusion-exclusion expansion of r_{C,c0} according to canonical 2-trees and then proving a correlation-decay bound in the counting LLL regime. The randomized algorithm turns this recursion into an unbiased estimator whose second moment and expected running time are controlled by a subcritical branching process; the final counting estimator is assembled via constraint-wise self-reducibility.

Significance. If correct, the paper closes the algorithmic gap for approximate counting of general CSPs from pD^5 to the optimal pD^2 scale, matching known hardness results up to constant factors. The deterministic result matches the state of the art for deterministic counting in the local lemma regime, and the randomized algorithm achieves a poly(k,D,q)(n/ε)^2 bound under a weak evaluation oracle, which appears to be new at this threshold. The derivation is self-contained: numerical constants are fixed by elementary inequalities, no free parameters are fitted, and the target theorem is not assumed. The 2-tree expansion and its correlation-decay analysis are structurally novel relative to the existing cluster-expansion and recursion-based counting LLL literature, and they are likely to be useful beyond the particular algorithms presented here.

minor comments (6)
  1. [§5.2.2, Lemma 5.6] The off-diagonal bound P[E_T^1 ∩ E_T'^1] ≤ p^{|T∪T'|} is correct because Algorithm 2 samples the local configurations σ_c independently for every constraint c, so the violation events for the constraints in T∪T' are independent even when the constraints share variables. Please add one explicit sentence stating this independence, since the current wording leaves room for the misreading that σ_c are projections of a single global assignment.
  2. [Algorithm 2, line 4] The notation σ_{vbl(T)} should be defined explicitly as the tuple of the independently generated local configurations on the disjoint variable sets vbl(c) for c∈T; this is well-defined precisely because T is an independent set in the dependency graph.
  3. [§5.1, equation (26)] The equality P[∧_{c∈T}¬c ∧ free1(T) | C\Γ^{≤2}_C(T)] = P[∧_{c∈T}¬c ∧ free1(T)] relies on the fact that constraints at distance at least 3 from T have no variables in common with T∪free1(T); please state this independence explicitly, as it is essential to the alternative recursion.
  4. [Abstract and Condition 1.1] The condition 4e·p·(D+1) 2≤1 is missing the superscript in the rendering; it should read 4e·p·(D+1)^2≤1.
  5. [§1.1, equation (1)] The hardness statement pD^2 < 4e^2 is easy to misread as a tractability condition; the surrounding text makes clear that hardness holds beyond this bound, but the equation itself should be phrased as 'pD^2 ≳ 1 is necessary for tractability' or accompanied by an explicit sentence to avoid confusion.
  6. [§4.1, Lemma 4.2] The incidence-counting argument bounding |free1(T)| ≤ (D−1)|T|+1 is correct, but it would benefit from one extra sentence noting that each of the at least |T|−1 distinct distance-one constraints used to connect T in G^2 consumes one incidence, so they are counted separately from the remaining neighbor incidences.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the counting LLL derivation is self-contained and the off-diagonal correlation concern is resolved by independent per-constraint sampling.

full rationale

The derivation is self-contained. The main identity is Lemma 3.5 (Eq. 10), obtained by regrouping the standard inclusion-exclusion expansion (Eq. 9) via the canonical 2-tree map Tree(·) and the exact preimage characterization Lemma 3.4; no target quantity is assumed among the hypotheses. The deterministic estimator (Eq. 21) is a truncation of that identity, with error controlled by the correlation-decay Lemma 3.6, whose proof uses only Theorem 2.2 from HSS11, the subgraph counting lemma Lemma 2.5, and elementary inequalities. The randomized estimator RandMargEst is proven unbiased by substituting Lemma 5.1 (another exact regrouping of the same inclusion-exclusion expansion) and the Russian-roulette reciprocal estimator Lemma 5.5; the variance and efficiency bounds use only the independent per-constraint sampling in Algorithm 2 line 1, which gives P[all constraints in S violated] = ∏_{c∈S} P[¬c] = p^{|S|} for any set S, including non-independent sets. This resolves the off-diagonal correlation concern: duplicate or overlapping constraints cannot create positive correlation because each constraint's violation event is determined by its own independent sample. Numerical constants are fixed by elementary inequalities under Condition 1.1; nothing is fitted to data, and no result is imported from the same-author citations as a load-bearing premise. Citations to [WY24, HWY23a, FGW+25] are used for context, notation, and prior bounds, not as inputs to the proof; no uniqueness theorem or ansatz is smuggled in from same-author work.

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

No free parameters are fitted to data; all constants are fixed by inequalities. The only new postulated object is the mathematical 2-tree expansion itself, which is not an invented physical entity. The main premises are the oracle model and the external hardness conversion.

assumptions (4)
  • domain assumption Evaluation oracle (Assumption 1): constraint functions are accessed through an oracle that returns satisfaction in one unit of time regardless of width k.
    The cost bounds count oracle calls as unit operations; this is not justified for superconstant width except by assumption.
  • standard math Lovász Local Lemma and the conditional probability bound of Haeupler, Saha, and Srinivasan (Theorem 2.2).
    Used to bound marginal probabilities and to obtain the correlation decay estimates in Lemma 3.1 and Lemma 3.6.
  • standard math The number of 2-trees of size t containing a fixed vertex is at most (e D^2)^(t-1).
    Derived from the connected subgraph bound of BCKL13 and used throughout the convergence and cost analyses.
  • domain assumption The cited hardness results of BGG+19 and GGW23 translate to the condition pD^2 < 4e^2 under the paper's definition of dependency degree.
    The footnote asserts this translation but gives no derivation, and with D as defined in the paper the translation is not immediate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Counting Lov\'asz Local Lemma." pith.science (2026). https://pith.science/paper/EZQM5NLQ

@misc{pith2026260808616,
  author       = {Pith},
  title        = {Pith review of: A Counting Lov\'asz Local Lemma},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EZQM5NLQ}},
  note         = {Machine review of arXiv:2608.08616}
}
abstract

We establish a counting analogue of the Lov\'asz Local Lemma: we give polynomial-time algorithms for approximately counting satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime $$ 4 \mathrm{e}\cdot p\cdot (D+1)^2\leq 1, $$ where $p$ is the maximum constraint violation probability and $D$ is the maximum dependency degree. This condition is tight up to constant factors, matching known lower bounds $pD^2\gtrsim 1$ for approximate counting in natural subclasses of CSPs. The core of our approach is a novel $2$-tree expansion for constraint marginal probabilities, which captures the decay of correlations in the local lemma regime.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

289 extracted references · 61 canonical work pages

  1. [2]

    Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels , year =

    Abraham, Ittai and Chechik, Shiri and Gavoille, Cyril , booktitle =. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels , year =

  2. [3]

    and Moore, C

    Achlioptas, D. and Moore, C. , booktitle =. The asymptotic order of the random k -. 2002 , volume =. doi:10.1109/SFCS.2002.1182003 , publisher =

    arXiv 2002

  3. [4]

    On the 2-Colorability of Random Hypergraph , booktitle =

    Achlioptas, Dimitris and Moore, Cristopher , editor =. On the 2-Colorability of Random Hypergraph , booktitle =. 2002 , pages =

    2002

  4. [5]

    2003 , isbn =

    Achlioptas, Dimitris and Peres, Yuval , title =. 2003 , isbn =. doi:10.1145/780542.780577 , booktitle =

    arXiv 2003

  5. [6]

    2006 , isbn =

    Achlioptas, Dimitris and Ricci-Tersenghi, Federico , title =. 2006 , isbn =. doi:10.1145/1132516.1132537 , booktitle =

    arXiv 2006

  6. [7]

    FOCS , title =

    Achlioptas, Dimitris and. FOCS , title =. 2008 , volume =

    2008

  7. [8]

    2016 , publisher =

    Achlioptas, Dimitris and Iliopoulos, Fotis , title =. 2016 , publisher =. doi:10.1145/2818352 , journal =

    work page doi:10.1145/2818352 2016

  8. [9]

    FOCS , author =

    The asymptotic order of the random k -. FOCS , author =

Show all 289 references
  1. [10]

    arXiv preprint arXiv:2407.16627 , year =

    Hardness of sampling solutions from the Symmetric Binary Perceptron , author =. arXiv preprint arXiv:2407.16627 , year =

    arXiv

  2. [11]

    Beyond the

    Achlioptas, Dimitris and Iliopoulos, Fotis and Sinclair, Alistair , booktitle =. Beyond the. 2019 , volume =

    2019

  3. [12]

    STOC , pages =

    Alev, Vedat Levi and Lau, Lap Chi , title =. STOC , pages =. 2020 , isbn =. doi:10.1145/3357713.3384317 , abstract =

    2020

  4. [13]

    , title =

    Alon, Noga and Spencer, Joel H. , title =. 2016 , isbn =

    2016

  5. [14]

    A parallel algorithmic version of the local lemma , volume =

    Alon, Noga , journal =. A parallel algorithmic version of the local lemma , volume =. 1991 , doi =

    1991

  6. [15]

    Mixing properties of colourings of the. Comb. Probab. Comput. , author =. 2021 , pages =. doi:10.1017/S0963548320000395 , number =

    2021 doi

  7. [16]

    Log-concave polynomials

    Nima Anari and Kuikui Liu and Shayan. Log-concave polynomials. STOC , doi =

  8. [17]

    Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing , volume =

    Anand, Konrad and Jerrum, Mark , doi =. Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing , volume =. SIAM J. Comput. , number =. 2022 , bdsk-url-1 =

    2022

  9. [20]

    2022 , isbn =

    Anari, Nima and Jain, Vishesh and Koehler, Frederic and Pham, Huy Tuan and Vuong, Thuy-Duong , title =. 2022 , isbn =. doi:10.1145/3519935.3520048 , booktitle =

    2022

  10. [21]

    and Vuong, Thuy-Duong , booktitle =

    Anari, Nima and Liu, Yang P. and Vuong, Thuy-Duong , booktitle =. Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence , year =

  11. [22]

    Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model , journal =

    Anari, Nima and Liu, Kuikui and. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model , journal =. 2024 , doi =. https://doi.org/10.1137/20M1367696 , note =

    2024 doi

  12. [23]

    2024 , isbn =

    Anari, Nima and Koehler, Frederic and Vuong, Thuy-Duong , title =. 2024 , isbn =. doi:10.1145/3618260.3649622 , booktitle =

    2024

  13. [24]

    Nicholas J. A. Harvey and Jan Vondr. An Algorithmic Proof of the Lopsided Lovasz Local Lemma , journal =. 2015 , url =

    2015

  14. [25]

    Sanjeev Arora and Boaz Barak , title =

  15. [26]

    Hypergraph coloring up to condensation , journal =

    Ayre, Peter and. Hypergraph coloring up to condensation , journal =. doi:https://doi.org/10.1002/rsa.20824 , url =

    doi

  16. [27]

    Random Struct

    Bandyopadhyay, Antar and Gamarnik, David , title =. Random Struct. Algorithms , volume =. doi:https://doi.org/10.1002/rsa.20236 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20236 , abstract =

    doi

  17. [28]

    Comb., Prob

    Planting colorings Silently , volume =. Comb., Prob. and Comput. , author =. 2017 , pages =. doi:10.1017/S0963548316000390 , number =

    2017 doi

  18. [29]

    Correlation and

    Barthe, Franck and. Correlation and. Int. Math. Res. Not. , volume =. 2011 , publisher =. doi:10.1093/imrn/rnq174 , url =

    2011 doi

  19. [30]

    2016 , pages =

    Barvinok, Alexander , title =. 2016 , pages =. doi:10.1007/978-3-319-51829-9 , url =

    2016 doi

  20. [31]

    Barvinok, Alexander , title =. Found. Comput. Math. , fjournal =. 2016 , number =. doi:10.1007/s10208-014-9243-7 , url =

    2016 doi

  21. [32]

    Barvinok, Alexander , title =. Combin. Probab. Comput. , year =

  22. [33]

    STOC , pages =

    Bayati, Mohsen and Gamarnik, David and Katz, Dimitriy and Nair, Chandra and Tetali, Prasad , title =. STOC , pages =. 2007 , isbn =. doi:10.1145/1250790.1250809 , abstract =

    2007

  23. [34]

    doi:10.1145/3357713.3384244 , booktitle =

    Siddharth Bhandari and Sayantan Chakraborty , title =. doi:10.1145/3357713.3384244 , booktitle =

  24. [35]

    An algorithmic approach to the

    Beck, J. An algorithmic approach to the. Random Struct. Algorithms , number =. doi:10.1002/rsa.3240020402 , volume =

    doi

  25. [36]

    On zero-free regions for the anti-ferromagnetic

    Bencs, Ferenc and Davies, Ewan and Patel, Viresh and Regts, Guus , journal =. On zero-free regions for the anti-ferromagnetic. 2021 , publisher =

    2021

  26. [37]

    Glauber dynamics on trees and hyperbolic graphs , url =

    Berger, Noam and Kenyon, Claire and Mossel, Elchanan and Peres, Yuval , date-added =. Glauber dynamics on trees and hyperbolic graphs , url =. Probab. Theory Relat. Fields , number =. 2005 , bdsk-url-1 =. doi:10.1007/s00440-004-0369-4 , id =

    2005 doi

  27. [38]

    Accelerating simulated annealing for the permanent and combinatorial counting problems , journal =

    Bez\'. Accelerating simulated annealing for the permanent and combinatorial counting problems , journal =. 2008 , number =. doi:10.1137/050644033 , url =

    2008 doi

  28. [39]

    Computing the Volume is Difficult , doi =

    Imre B. Computing the Volume is Difficult , doi =. Discret. Comput. Geom. , volume =

  29. [40]

    Approximation via Correlation Decay When Strong Spatial Mixing Fails , volume =

    Ivona Bez. Approximation via Correlation Decay When Strong Spatial Mixing Fails , volume =. doi:10.1137/16M1083906 , year =

    doi

  30. [41]

    The algorithmic phase transition of random k -

    Bresler, Guy and Huang, Brice , booktitle =. The algorithmic phase transition of random k -. 2022 , doi =

    2022

  31. [42]

    An Improvement of the

    Bissacot, Rodrigo and Fern. An Improvement of the. Comb. Probab. Comput. , volume =. 2011 , publisher =. doi:10.1017/S0963548311000253 , url =

    2011 doi

  32. [43]

    doi:10.4230/LIPIcs.ITCS.2020.27 , booktitle =

    Amartya Shankha Biswas and Ronitt Rubinfeld and Anak Yodpinyanee , title =. doi:10.4230/LIPIcs.ITCS.2020.27 , booktitle =

    2020 doi

  33. [44]

    Entropy decay in the

    Blanca, Antonio and Caputo, Pietro and Parisi, Daniela and Sinclair, Alistair and Vigoda, Eric , booktitle =. Entropy decay in the. 2021 , doi =

    2021

  34. [45]

    SODA , year =

    Antonio Blanca and Pietro Caputo and Zongchen Chen and Daniel Parisi and Daniel Štefankovič and Eric Vigoda , title =. SODA , year =. doi:10.1137/1.9781611977073.145 , url =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.145 , publisher =

    doi

  35. [46]

    ACM Transactions on Algorithms , volume =

    Fast and perfect sampling of subgraphs and polymer systems , author =. ACM Transactions on Algorithms , volume =. 2024 , publisher =

    2024

  36. [47]

    , title =

    Blanchet, Jose and Chen, Nan and Glynn, Peter W. , title =. Proceedings of the 2015 Winter Simulation Conference , pages =. 2015 , doi =

    2015

  37. [48]

    Journal of Theoretical Probability , author =

    Modified Logarithmic. Journal of Theoretical Probability , author =. 2006 , pages =. doi:10.1007/s10959-006-0016-3 , url =

    2006 doi

  38. [49]

    ICALP , pages =

    Bordewich, Magnus and Dyer, Martin and Karpinski, Marek , title =. ICALP , pages =. 2006 , isbn =. doi:10.1007/11786986_11 , abstract =

    2006 doi

  39. [50]

    ALGORITHMS , year =

    Magnus Bordewich and Martin Dyer and Marek Karpinski , title =. ALGORITHMS , year =

  40. [51]

    Left and right convergence of graphs with bounded degree , journal =

    Borgs, Christian and Chayes, Jennifer and Kahn, Jeff and. Left and right convergence of graphs with bounded degree , journal =. 2013 , number =. doi:10.1002/rsa.20414 , url =

    2013 doi

  41. [52]

    Random Struct

    Borgs, Christian and Chayes, Jennifer and Helmuth, Tyler and Perkins, Will and Tetali, Prasad , title =. Random Struct. Algorithms , volume =. doi:https://doi.org/10.1002/rsa.21131 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.21131 , year =

    doi

  42. [53]

    Percolation and the hard-core lattice gas model , author =. Stoch. Process. Their Appl. , volume =. 1994 , publisher =

    1994

  43. [54]

    FOCS , publisher =

    Russ Bubley and Martin Dyer , title =. FOCS , publisher =. 1997 , pages =

    1997

  44. [55]

    2020 , doi =

    The Asymptotics of the Clustering Transition for Random Constraint Satisfaction Problems , author =. 2020 , doi =

    2020

  45. [56]

    , title =

    Bulatov, Andrei A. , title =. 2013 , issue_date =. doi:10.1145/2528400 , articleno =

    2013 doi

  46. [57]

    Bulatov , title =

    Andrei A. Bulatov , title =. FOCS , pages =. 2017 , doi =

    2017

  47. [58]

    2017 , issue_date =

    Cai, Jin-Yi and Chen, Xi , title =. 2017 , issue_date =. doi:10.1145/2822891 , articleno =

    2017 doi

  48. [59]

    SODA , pages =

    Cannon, Sarah and Perkins, Will , title =. SODA , pages =. 2020 , mrclass =

    2020

  49. [60]

    Caputo, Pietro and Menz, Georg and Tetali, Prasad , title =. Ann. Fac. Sci. Toulouse. Math. , pages =. 2015 , publisher =. doi:10.5802/afst.1460 , language =

    2015 doi

  50. [61]

    A sharp analog of

    Carlen, Eric A and Lieb, Elliott H and Loss, Michael , journal =. A sharp analog of. 2004 , publisher =

    2004

  51. [62]

    Subadditivity of the entropy and its relation to

    Carlen, Eric A and Cordero-Erausquin, Dario , journal =. Subadditivity of the entropy and its relation to. 2009 , publisher =

    2009

  52. [63]

    SODA , chapter =

    Charlie Carlson and Eric Vigoda , title =. SODA , chapter =. doi:10.1137/1.9781611978322.71 , url =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611978322.71 , year =

    doi

  53. [64]

    SODA , chapter =

    Charlie Carlson and Xiaoyu Chen and Weiming Feng and Eric Vigoda , title =. SODA , chapter =. doi:10.1137/1.9781611978322.184 , url =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611978322.184 , year =

    doi

  54. [65]

    Carter, L. L. and Cashwell, E. D. , year =. Particle-transport simulation with the. doi:10.2172/4167844 , url =

    doi

  55. [66]

    Cooper and Benjamin Doerr and Tobias Friedrich and Joel Spencer , title =

    Joshua N. Cooper and Benjamin Doerr and Tobias Friedrich and Joel Spencer , title =. Random Struct. Algorithms , doi =

  56. [67]

    Localization Schemes: A Framework for Proving Mixing Bounds for

    Yuansi Chen and Ronen Eldan , booktitle =. Localization Schemes: A Framework for Proving Mixing Bounds for. 2022 , volume =

    2022

  57. [68]

    Charting the replica symmetric phase , author =. Commun. Math. Phys. , volume =. 2018 , publisher =

    2018

  58. [69]

    Quasi-factorization of the entropy and logarithmic

    Cesi, Filippo , journal =. Quasi-factorization of the entropy and logarithmic. 2001 , volume =. doi:10.1007/PL00008792 , url =

    2001 doi

  59. [70]

    Coja-Oghlan, Amin and Frieze, Alan , title =. SIAM J. Comput. , volume =. 2014 , doi =

    2014

  60. [71]

    Chen and W

    X. Chen and W. Feng and Y. Yin and X. Zhang , booktitle =. Rapid mixing of Glauber dynamics via spectral independence for all degrees , year =. doi:10.1109/FOCS52979.2021.00022 , url =

    2021

  61. [72]

    Optimal mixing for two-state anti-ferromagnetic spin systems , year =

    Chen, Xiaoyu and Feng, Weiming and Yin, Yitong and Zhang, Xinyuan , booktitle =. Optimal mixing for two-state anti-ferromagnetic spin systems , year =

  62. [73]

    Modified log-

    Cryan, Mary and Guo, Heng and Mousa, Giorgos , fjournal =. Modified log-. Ann. Probab. , doi =

  63. [74]

    Chandrasekaran, Karthekeyan and Goyal, Navin and Haeupler, Bernhard , title =. SIAM J. Comput. , volume =. 2013 , doi =. https://doi.org/10.1137/100799642 , note =

    2013 doi

  64. [75]

    The Number of Random 2 -

    Chatterjee, Arnab and. The Number of Random 2 -. RANDOM 2024 , pages =. 2024 , publisher =. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.39 , annote =

    2024 doi

  65. [76]

    SODA , year =

    Sitan Chen and Michelle Delcourt and Ankur Moitra and Guillem Perarnau and Luke Postle , title =. SODA , year =. doi:10.1137/1.9781611975482.134 , url =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.134 , publisher =

    doi

  66. [77]

    Rapid Mixing of

    Chen, Zongchen and Liu, Kuikui and Vigoda, Eric , booktitle =. Rapid Mixing of. 2020 , volume =

    2020

  67. [79]

    Rapid Mixing for Colorings via Spectral Independence , year =

    Chen, Zongchen and Galanis, Andreas and. Rapid Mixing for Colorings via Spectral Independence , year =. SODA , pages =

  68. [80]

    doi:10.1137/1.9781611977554.ch132 , url =

    Zongchen Chen and Nitya Mani and Ankur Moitra , title =. doi:10.1137/1.9781611977554.ch132 , url =

    doi

  69. [81]

    Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications , year =

    Chen, Zongchen and Liu, Kuikui and Mani, Nitya and Moitra, Ankur , booktitle =. Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications , year =

  70. [82]

    STOC 2025 , url =

    Counting random k -SAT near the satisfiability threshold , author =. STOC 2025 , url =

    2025

  71. [83]

    Fast Sampling of Satisfying Assignments from Random

    Chen, Zongchen and Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Herrera-Poyatos, Andr. Fast Sampling of Satisfying Assignments from Random. SIAM J. Discrete Math. , volume =. 2024 , doi =

    2024

  72. [84]

    2025 , isbn =

    Chen, Zongchen and Lonkar, Aditya and Wang, Chunyang and Yang, Kuan and Yin, Yitong , title =. 2025 , isbn =. doi:10.1145/3717823.3718163 , booktitle =

    2025

  73. [85]

    ICALP , pages =

    Chen, Zejia and Wang, Yulin and Zhang, Chihao and Zhang, Zihan , title =. ICALP , pages =. 2025 , volume =. doi:10.4230/LIPIcs.ICALP.2025.54 , annote =

    2025 doi

  74. [86]

    2025 , eprint =

    Deterministic counting from coupling independence , author =. 2025 , eprint =

    2025

  75. [87]

    FOCS , publisher =

    Chen, Xiaoyu and Chen, Zongchen and Yin, Yitong and Zhang, Xinyuan , title =. FOCS , publisher =. 2025 , isbn =. doi:10.1145/3717823.3718260 , pages =

    2025

  76. [88]

    Rapid Mixing on Random Regular Graphs beyond Uniqueness , doi =

    Chen, Xiaoyu and Chen, Zejia and Chen, Zongchen and Yin, Yitong and Zhang, Xinyuan , year =. Rapid Mixing on Random Regular Graphs beyond Uniqueness , doi =. FOCS , pages =

  77. [89]

    Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for

    Xiaoyu Chen and Zhe Ju and Tianshun Miao and Yitong Yin and Xinyuan Zhang , year =. Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for. 2604.10525 , archiveprefix =

    arXiv

  78. [90]

    arXiv preprint arXiv:2604.02235 , year =

    Subquadratic Counting via Perfect Marginal Sampling , author =. arXiv preprint arXiv:2604.02235 , year =

  79. [91]

    Chen, Zongchen and Liu, Kuikui and Mani, Nitya and Moitra, Ankur , year = 2023, month = nov, pages =. Strong. 2023. doi:10.1109/FOCS57990.2023.00053 , isbn =

    2023

  80. [92]

    A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations , url =

    Chernoff, Herman , doi =. A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations , url =. Ann. Math. Statist. , number =

  81. [93]

    Distributed algorithms for the Lovász Local Lemma and graph coloring , isbn =

    Chung, Kai-Min and Pettie, Seth and Su, Hsin-Hao , year =. Distributed algorithms for the Lovász Local Lemma and graph coloring , isbn =. PODC , doi =

  82. [94]

    STOC , pages =

    Information-theoretic thresholds from the cavity method , author =. STOC , pages =

  83. [95]

    Belief propagation guided decimation fails on random formulas , author =. J. ACM , volume =. 2017 , publisher =

    2017

  84. [96]

    A Better Algorithm for Random k -. SIAM J. Comput. , volume =. 2010 , doi =

    2010

  85. [97]

    The Decimation Process in Random k -. SIAM J. Disc. Math. , volume =. 2012 , doi =

    2012

  86. [99]

    Belief propagation on the random k -

    Amin. Belief propagation on the random k -. Ann. Appl. Probab. , number =. 2022 , doi =

    2022

  87. [100]

    , title =

    Cook, Stephen A. , title =. STOC , pages =. 1971 , isbn =. doi:10.1145/800157.805047 , abstract =

    1971

  88. [101]

    Random Struct

    Czumaj, Artur and Scheideler, Christian , title =. Random Struct. Algorithms , volume =. 2000 , number =. doi:10.1002/1098-2418(200010/12)17:3/4<213::AID-RSA3>3.0.CO;2-Y , note =

    2000 doi

  89. [102]

    Cooper and Joel Spencer , title =

    Joshua N. Cooper and Joel Spencer , title =. Comb. Probab. Comput. , doi =

  90. [103]

    SODA , pages =

    A near-linear time sampler for the Ising model with external field , author =. SODA , pages =. 2023 , organization =

    2023

  91. [104]

    Pairs of SAT Assignments and Clustering in Random Boolean Formulae , volume =

    Daudé, Hervé and Mezard, Marc and Mora, Thierry and Zecchina, Riccardo , year =. Pairs of SAT Assignments and Clustering in Random Boolean Formulae , volume =. Theore. Comput. Sci. , doi =

  92. [106]

    Random Struct

    Delcourt, Michelle and Heinrich, Marc and Perarnau, Guillem , title =. Random Struct. Algorithms , volume =. doi:https://doi.org/10.1002/rsa.20960 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20960 , abstract =

    doi

  93. [108]

    2014 , isbn =

    Ding, Jian and Sly, Allan and Sun, Nike , title =. 2014 , isbn =. doi:10.1145/2591796.2591862 , booktitle =

    2014

  94. [109]

    Jian Ding and Allan Sly and Nike Sun , title =. Ann. Math. , number =. 2022 , doi =

    2022

  95. [110]

    Dobrushin, R. L. , title =. Theory of Probability & Its Applications , volume =. 1970 , doi =

    1970

  96. [111]

    and Kleinberg, Robert and Niazadeh, Rad , title =

    Dughmi, Shaddin and Hartline, Jason D. and Kleinberg, Robert and Niazadeh, Rad , title =. STOC , pages =. 2017 , mrclass =

    2017

  97. [112]

    Dyer, Martin and Frieze, Alan and Kannan, Ravi , title =. J. ACM , fjournal =. 1991 , number =. doi:10.1145/102782.102783 , url =

    1991

  98. [113]

    Dyer, Martin and Richerby, David , title =. SIAM J. Comput. , volume =. 2013 , doi =

    2013

  99. [114]

    2015 , volume =

    Dyer, Martin and Frieze, Alan and Greenhill, Catherine , title =. 2015 , volume =. doi:10.1016/j.jctb.2015.01.002 , journal =

    2015 doi

  100. [115]

    An Information-Theoretic View of Stochastic Localization , year =

    El Alaoui, Ahmed and Montanari, Andrea , journal =. An Information-Theoretic View of Stochastic Localization , year =

  101. [116]

    A geometric inequality and the complexity of computing volume , doi =

    Elekes, Gy. A geometric inequality and the complexity of computing volume , doi =. Discret. Comput. Geom. , volume =. 1986 , publisher =

    1986

  102. [117]

    Choosability in graphs , author =. Proc. West Coast Conf. Combinatorics, Graph Theory and Computing , volume =. 1980 , organization =

    1980

  103. [118]

    The Computational Structure of Monotone Monadic

    Tom. The Computational Structure of Monotone Monadic. 1998 , doi =

    1998

  104. [119]

    STOC , pages =

    Sampling constraint satisfaction solutions in the local lemma regime , author =. STOC , pages =. doi:10.1145/3406325.3451101 , year =

  105. [120]

    Improved Bounds for Randomly colouring Simple Hypergraphs , doi =

    Weiming Feng and Heng Guo and Jiaheng Wang , booktitle =. Improved Bounds for Randomly colouring Simple Hypergraphs , doi =

  106. [121]

    RANDOM , fjournal =

    Feng, Weiming and Guo, Heng and Yin, Yitong , title =. RANDOM , fjournal =. 2022 , number =

    2022

  107. [122]

    2022 , publisher =

    Feng, Weiming and Guo, Heng and Yin, Yitong and Zhang, Chihao , title =. 2022 , publisher =. doi:10.1145/3531008 , journal =

    2022 doi

  108. [123]

    Towards derandomising

    Feng, Weiming and Guo, Heng and Wang, Chunyang and Wang, Jiaheng and Yin, Yitong , booktitle =. Towards derandomising. 2023 , volume =

    2023

  109. [124]

    Feng, Weiming and Guo, Heng and Wang, Chunyang and Wang, Jiaheng and Yin, Yitong , title =. SIAM J. Comput. , volume =. 2025 , doi =

    2025

  110. [125]

    Antiferromagnetic Potts Models on the Square Lattice: A High-Precision

    Ferreira, Sabino Jos. Antiferromagnetic Potts Models on the Square Lattice: A High-Precision. J. Stat. Phys. , year =. doi:10.1023/A:1004599121565 , url =. cond-mat/9811345 , archiveprefix =

    arXiv

  111. [126]

    Fast sampling and counting

    Feng, Weiming and Guo, Heng and Yin, Yitong and Zhang, Chihao , fjournal =. Fast sampling and counting. J. ACM , number =. doi:10.1145/3469832 , note =

    doi

  112. [127]

    An interruptible algorithm for perfect sampling via

    Fill, James Allen , booktitle =. An interruptible algorithm for perfect sampling via

  113. [128]

    Extension of

    Fill, James Allen and Machida, Motoya and Murdoch, Duncan J and Rosenthal, Jeffrey S , journal =. Extension of

  114. [129]

    and Huber, Mark , booktitle =

    Fill, James A. and Huber, Mark , booktitle =. The randomness recycler: a new technique for perfect sampling , doi =

  115. [130]

    PNAS , volume =

    Florent Krzakala and Andrea Montanari and Federico Ricci-Tersenghi and Guilhem Semerjian and Lenka Zdeborová , title =. PNAS , volume =. 2007 , doi =

    2007

  116. [131]

    Sharp Thresholds of Graph Properties, and the k -

    Ehud Friedgut and Jean Bourgain , journal =. Sharp Thresholds of Graph Properties, and the k -

  117. [132]

    Journal of Algorithms , volume =

    Analysis of Two Simple Heuristics on a Random Instance of k -. Journal of Algorithms , volume =. 1996 , issn =

    1996

  118. [133]

    Randomly coloring simple hypergraphs , journal =

    Alan Frieze and Páll Melsted , keywords =. Randomly coloring simple hypergraphs , journal =. 2011 , issn =. doi:https://doi.org/10.1016/j.ipl.2011.06.001 , url =

    2011 doi

  119. [134]

    Randomly coloring simple hypergraphs with fewer colors , journal =

    Alan Frieze and Michael Anastos , keywords =. Randomly coloring simple hypergraphs with fewer colors , journal =. 2017 , issn =. doi:https://doi.org/10.1016/j.ipl.2017.06.005 , url =

    2017 doi

  120. [135]

    Vishnoi and Yitong Yin , booktitle =

    Weiming Feng and Nisheeth K. Vishnoi and Yitong Yin , booktitle =. Dynamic sampling from graphical models , doi =

  121. [136]

    Inapproximability of the partition function for the antiferromagnetic

    Galanis, Andreas and. Inapproximability of the partition function for the antiferromagnetic. Comb. Probab. Comput. , number =

  122. [137]

    arXiv , author =:2206.15308 , journal =

    Fast sampling of satisfying assignments from random k -SAT , volume =. arXiv , author =:2206.15308 , journal =

    arXiv

  123. [138]

    2023 , issue_date =

    Galanis, Andreas and Guo, Heng and Wang, Jiaheng , title =. 2023 , issue_date =. doi:10.1145/3558554 , journal =

    2023 doi

  124. [140]

    Correlation decay and deterministic FPTAS for counting colorings of a graph , journal =

    David Gamarnik and Dmitriy Katz , keywords =. Correlation decay and deterministic FPTAS for counting colorings of a graph , journal =. 2012 , note =. doi:https://doi.org/10.1016/j.jda.2010.10.002 , url =

    2012 doi

  125. [141]

    Random Struct

    Strong spatial mixing of list coloring of graphs , author =. Random Struct. Algorithms , volume =. 2015 , publisher =

    2015

  126. [142]

    PNAS , volume =

    The overlap gap property: A topological barrier to optimizing over random structures , author =. PNAS , volume =. 2021 , publisher =

    2021

  127. [143]

    Reconstruction for Models on Random Graphs , year =

    Gerschenfeld, Antonine and Montanari, Andrea , booktitle =. Reconstruction for Models on Random Graphs , year =

  128. [144]

    Counting solutions to random

    Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Yang, Kuan , journal =. Counting solutions to random. 2021 , publisher =

    2021

  129. [145]

    Guo, Heng and Jerrum, Mark and Liu, Jingcheng , title =. J. ACM , fjournal =. 2019 , number =. doi:10.1145/3310131 , note =

    2019 doi

  130. [146]

    Exact estimation for

    Glynn, Peter W and Rhee, Chang-han , journal =. Exact estimation for. 2014 , publisher =

    2014

  131. [147]

    Goldberg, Leslie Ann and Martin, Russell and Paterson, Mike , title =. SIAM J. Comput. , volume =. 2005 , doi =. https://doi.org/10.1137/S0097539704445470 , note =

    2005 doi

  132. [148]

    Random Struct

    Goldberg, Leslie Ann and Jerrum, Mark and Karpinski, Marek , title =. Random Struct. Algorithms , pages =. 2010 , address =

    2010

  133. [149]

    Parikshit Gopalan and Raghu Meka and Omer Reingold , title =. Comput. Complex. , doi =

  134. [150]

    Non-linear Log-. Commun. Math. Phys. , author =. 2023 , pages =. doi:10.1007/s00220-023-04851-1 , number =

    2023 doi

  135. [151]

    Counting hypergraph colorings in the local lemma regime , author =. SIAM J. Comput. , volume =. 2019 , doi =

    2019

  136. [152]

    Guo, Heng and Jerrum, Mark , title =. SIAM J. Comput. , fjournal =. 2019 , number =

    2019

  137. [153]

    RANDOM , volume =

    Guo, Heng and He, Kun , title =. RANDOM , volume =. 2020 , number =

    2020

  138. [154]

    , title =

    Heng Guo and Vishvajeet N. , title =. ITCS , pages =. 2025 , doi =

    2025

  139. [155]

    Bernhard Haeupler and Barna Saha and Aravind Srinivasan , title =. J. 2011 , doi =

    2011

  140. [156]

    Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs , volume =

    Haeupler, Bernhard and Harris, David , year =. Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs , volume =. ACM Transactions on Algorithms , doi =

  141. [157]

    Scandinavian Journal of Statistics , volume =

    On exact simulation of Markov random fields using coupling from the past , author =. Scandinavian Journal of Statistics , volume =. 1999 , publisher =

    1999

  142. [158]

    and Srinivasan, Aravind , title =

    Harris, David G. and Srinivasan, Aravind , title =. 2017 , issue_date =. doi:10.1145/3039869 , journal =

    2017 doi

  143. [160]

    Random Struct

    New bounds for the Moser-Tardos distribution , author =. Random Struct. Algorithms , volume =. 2020 , doi =

    2020

  144. [161]

    , title =

    Harris, David G. , title =. 2021 , issue_date =. doi:10.1145/3392035 , journal =

    2021 doi

  145. [162]

    , title =

    Harris, David G. , title =. Random Struct. Algorithms , volume =. doi:https://doi.org/10.1002/rsa.21152 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.21152 , year =

    doi

  146. [163]

    Nicholas J. A. Harvey and Piyush Srivastava and Jan Vondr. Computing the Independence Polynomial: from the Tree Threshold down to the Roots , booktitle =. 2018 , url =

    2018

  147. [164]

    Harvey, Nicholas J. A. and Vondr. An Algorithmic Proof of the. SIAM J. Comput. , volume =. 2020 , doi =. https://doi.org/10.1137/18M1167176 , note =

    2020 doi

  148. [165]

    HASTINGS, W. K. , title =. Biometrika , volume =. 1970 , issn =

    1970

  149. [166]

    Random Struct

    Hatami, Hamed and Molloy, Michael , title =. Random Struct. Algorithms , volume =. doi:https://doi.org/10.1002/rsa.20225 , url =

    doi

  150. [167]

    Hayes and Alistair Sinclair , journal =

    Thomas P. Hayes and Alistair Sinclair , journal =. A General Lower Bound for Mixing of Single-Site Dynamics on Graphs , urldate =

  151. [168]

    FOCS , pages =

    He, Kun and Li, Liang and Liu, Xingwu and Wang, Yuyi and Xia, Mingji , title =. FOCS , pages =. 2017 , mrclass =. doi:10.1109/FOCS.2017.48 , url =

    2017 doi

  152. [169]

    SODA , publisher =

    Kun He and Chunyang Wang and Yitong Yin , title =. SODA , publisher =. 2023 , doi =

    2023

  153. [170]

    Sampling

    He, Kun and Wang, Chunyang and Yin, Yitong , booktitle =. Sampling. 2022 , volume =

    2022

  154. [171]

    SODA , publisher =

    Kun He and Kewen Wu and Kuan Yang , title =. SODA , publisher =. 2023 , doi =

    2023

  155. [172]

    SODA , chapter =

    Kun He and Qian Li and Xiaoming Sun , title =. SODA , chapter =. doi:10.1137/1.9781611977554.ch129 , publisher =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch129 , year =

    doi

  156. [173]

    SODA , chapter =

    Kun He and Zhidan Li and Guoliang Qiu and Chihao Zhang , title =. SODA , chapter =. 2025 , doi =

    2025

  157. [174]

    Variable version

    Kun He and Liang Li and Xingwu Liu and Yuyi Wang and Mingji Xia , keywords =. Variable version. IANDC , volume =. 2026 , issn =. doi:https://doi.org/10.1016/j.ic.2025.105386 , url =

    2026

  158. [175]

    2020 , eprint =

    Marc Heinrich , title =. 2020 , eprint =

    2020

  159. [176]

    Algorithmic

    Helmuth, Tyler and Perkins, Will and Regts, Guus , journal =. Algorithmic. 2020 , publisher =

    2020

  160. [177]

    Jonathan Hermon and Justin Salez , title =. Ann. Appl. Probab. , number =. 2023 , doi =

    2023

  161. [178]

    ICALP , year =

    Analysing Survey Propagation Guided Decimationon Random Formulas , author =. ICALP , year =

  162. [179]

    Journal of the American Statistical Association , volume =

    A generalization of sampling without replacement from a finite universe , author =. Journal of the American Statistical Association , volume =. 1952 , publisher =

    1952

  163. [180]

    and Srinivasan, Aravind , title =

    Harris, David G. and Srinivasan, Aravind , title =. Theory Comput. , fjournal =. 2017 , pages =. doi:10.4086/toc.2017.v013a017 , url =

    2017 doi

  164. [181]

    and Srinivasan, Aravind , title =

    Harris, David G. and Srinivasan, Aravind , title =. J. ACM , fjournal =. 2019 , number =. doi:10.1145/3342222 , url =

    2019 doi

  165. [182]

    arXiv , author =:2107.03932 , journal =

    Perfect sampling for (atomic). arXiv , author =:2107.03932 , journal =

    arXiv

  166. [183]

    Rapid mixing of hypergraph independent sets , volume =

    Jonathan Hermon and Allan Sly and Yumeng Zhang , journal =. Rapid mixing of hypergraph independent sets , volume =

  167. [184]

    Huber, Mark , title =. Combin. Probab. Comput. , fjournal =. 2016 , number =

    2016

  168. [185]

    Exact sampling and approximate counting techniques , year =

    Huber, Mark , booktitle =. Exact sampling and approximate counting techniques , year =

  169. [186]

    Perfect sampling using bounding chains , volume =

    Huber, Mark , journal =. Perfect sampling using bounding chains , volume =

  170. [187]

    Huber, Mark , title =. Ann. Appl. Probab. , fjournal =. 2015 , number =. doi:10.1214/14-AAP1015 , url =

    2015 doi

  171. [188]

    Jenssen, Matthew and Keevash, Peter and Perkins, Will , title =. SIAM J. Comput. , fjournal =. 2020 , number =. doi:10.1137/19M1286669 , url =

    2020 doi

  172. [189]

    Surveys in Combinatorics 2024 , editor =

    Jenssen, Matthew , title =. Surveys in Combinatorics 2024 , editor =. 2024 , doi =

    2024

  173. [190]

    and Valiant, Leslie G

    Jerrum, Mark R. and Valiant, Leslie G. and Vazirani, Vijay V. , title =. Theoret. Comput. Sci. , fjournal =. 1986 , number =. doi:10.1016/0304-3975(86)90174-X , url =

    1986 doi

  174. [191]

    Random Struct

    Jerrum, Mark , title =. Random Struct. Algorithms , volume =. doi:https://doi.org/10.1002/rsa.3240070205 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.3240070205 , abstract =

    doi

  175. [192]

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

    Jerrum, Mark and Sinclair, Alistair and Vigoda, Eric , journal =. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries , volume =. doi:10.1145/1008731.1008738 , number =

  176. [193]

    arXiv preprint arXiv:2106.07744 , eprint =

    Fundamentals of Partial Rejection Sampling , author =. arXiv preprint arXiv:2106.07744 , eprint =

    arXiv

  177. [194]

    doi:10.1137/1.9781611977073.24 , booktitle =

    Matthew Jenssen and Aditya Potukuchi and Will Perkins , title =. doi:10.1137/1.9781611977073.24 , booktitle =

    doi

  178. [195]

    Approximate counting and sampling via local central limit theorems , booktitle =

    Vishesh Jain and Will Perkins and Ashwin Sah and Mehtaab Sawhney , doi =. Approximate counting and sampling via local central limit theorems , booktitle =

  179. [196]

    Polynomial-Time Approximation Algorithms for the

    Mark Jerrum and Alistair Sinclair , journal =. Polynomial-Time Approximation Algorithms for the

  180. [198]

    1949 , note =

    Herman Kahn , title =. 1949 , note =

    1949

  181. [199]

    1956 , note =

    Herman Kahn , title =. 1956 , note =

    1956

  182. [200]

    , editor =

    Karp, Richard M. , editor =. Reducibility among Combinatorial Problems , booktitle =. 1972 , publisher =. doi:10.1007/978-1-4684-2001-2_9 , url =

    1972 doi

  183. [201]

    F. P. Kelly , journal =. Stochastic Models of Computer Communication Systems , urldate =

  184. [202]

    1980 , issn =

    Polynomial algorithms in linear programming , journal =. 1980 , issn =. doi:https://doi.org/10.1016/0041-5553(80)90061-0 , url =

    1980 doi

  185. [203]

    and Kranakis, Evangelos and Krizanc, Danny and Stamatiou, Yannis C

    Kirousis, Lefteris M. and Kranakis, Evangelos and Krizanc, Danny and Stamatiou, Yannis C. , title =. Random Struct. Algorithms , volume =. doi:https://doi.org/10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U , year =

    doi

  186. [204]

    Moser and

    Kashyap Babu Rao Kolipaka and Mario Szegedy , booktitle =. Moser and. doi:10.1145/1993636.1993669 , year =

  187. [205]

    A Faster Approximation Algorithm for the

    Kolmogorov, Vladimir , booktitle =. A Faster Approximation Algorithm for the. 2018 , editor =

    2018

  188. [206]

    Kolmogorov, Vladimir , title =. SIAM J. Comput. , volume =. 2018 , doi =. https://doi.org/10.1137/16M1093306 , note =

    2018 doi

  189. [207]

    Cluster expansion for abstract polymer models , journal =

    Koteck. Cluster expansion for abstract polymer models , journal =

  190. [208]

    Krom, M. R. , title =. Mathematical Logic Quarterly , volume =. doi:https://doi.org/10.1002/malq.19670130104 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/malq.19670130104 , year =

    doi

  191. [209]

    Lenka Zdeborová and Florent Krzakala , title =. Adv. Phys. , volume =. 2016 , doi =

    2016

  192. [210]

    and Peres, Yuval , publisher =

    Levin, David A. and Peres, Yuval , publisher =. Markov chains and mixing times , year =

  193. [211]

    SODA , pages =

    Li, Liang and Lu, Pinyan and Yin, Yitong , title =. SODA , pages =. 2013 , isbn =

    2013

  194. [212]

    Liu, Jingcheng and Sinclair, Alistair and Srivastava, Piyush , title =. SIAM J. Comput. , pages =. 2019 , doi =

    2019

  195. [213]

    STOC , pages =

    Simple Parallel Algorithms for Single-Site Dynamics , author =. STOC , pages =. doi:10.1145/3519935.3519999 , year =

  196. [214]

    Phase Transitions via Complex Extensions of Markov Chains , booktitle =

    Jingcheng Liu and Chunyang Wang and Yitong Yin and Yixiao Yu , author+an =. Phase Transitions via Complex Extensions of Markov Chains , booktitle =

  197. [215]

    Liu, Jingcheng and Sinclair, Alistair and Srivastava, Piyush , title =. SIAM J. Comput. , volume =. 2025 , doi =. https://doi.org/10.1137/20M1317384 , note =

    2025 doi

  198. [216]

    Liu, Hongyang and Yin, Yitong , title =. J. ACM , articleno =. 2025 , publisher =. doi:10.1145/3708558 , abstract =

    2025 doi

  199. [217]

    SODA , pages =

    Hongyang Liu and Chunyang Wang and Yitong Yin , title =. SODA , pages =. 2026 , doi =

    2026

  200. [218]

    Problems and results on 3-chromatic Hypergraphs and some related questions , url =

    Erd. Problems and results on 3-chromatic Hypergraphs and some related questions , url =. Infinite and finite sets, volume 10 of Colloquia Mathematica Societatis J\'anos Bolyai , pages =

  201. [219]

    2013 , url =

    Pinyan Lu and Yitong Yin , title =. 2013 , url =. doi:10.1007/978-3-642-40328-6\_44 , timestamp =

    2013 doi

  202. [220]

    ISTCS , doi =

    Michael Luby and Boban Velickovic and Avi Wigderson , title =. ISTCS , doi =

  203. [221]

    STOC , doi =

    Michael Luby and Boban Velickovic , title =. STOC , doi =

  204. [222]

    and Molloy, M

    Lucier, B. and Molloy, M. , title =. SIAM J. Discrete Math. , volume =. 2011 , doi =

    2011

  205. [223]

    Torpid mixing of the

    Tomasz. Torpid mixing of the. J. Discrete Algorithms , volume =. 2005 , issn =. doi:https://doi.org/10.1016/j.jda.2004.05.002 , url =

    2005 doi

  206. [224]

    2018 , publisher =

    Lv, Jian-Ping and Deng, Youjin and Jacobsen, Jesper Lykke and Salas, Jesús , title =. 2018 , publisher =. doi:10.1088/1751-8121/aad1fe , url =

    2018 doi

  207. [225]

    Lyne, Anne-Marie and Girolami, Mark and Atchad. On. Stat. Sci. , volume =. 2015 , doi =

    2015

  208. [226]

    2025 , eprint =

    Approximate Counting in Local Lemma Regimes , author =. 2025 , eprint =

    2025

  209. [227]

    and Olivieri, E

    Martinelli, F. and Olivieri, E. , journal =. Approach to equilibrium of. 1994 , volume =. doi:10.1007/BF02101929 , url =

    1994 doi

  210. [228]

    Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Martinelli, Fabio and Sinclair, Alistair and Weitz, Dror , title =. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2004 , isbn =

    2004

  211. [229]

    Logarithmic

    Marton, Katalin , journal =. Logarithmic. 2004 , publisher =

    2004

  212. [230]

    1977 , publisher =

    Statistical Mechanics , author =. 1977 , publisher =

    1977

  213. [231]

    Monte Carlo Methods Appl

    Don McLeish , title =. Monte Carlo Methods Appl. , volume =. 2011 , doi =

    2011

  214. [232]

    Entropy of the

    Monasson, R\'emi and Zecchina, Riccardo , journal =. Entropy of the. 1996 , publisher =. doi:10.1103/PhysRevLett.76.3881 , url =

    1996 doi

  215. [233]

    Mézard and G

    M. Mézard and G. Parisi and R. Zecchina , title =. Science , volume =. 2002 , doi =

    2002

  216. [234]

    Clustering of Solutions in the Random Satisfiability Problem , author =. Phys. Rev. Lett. , volume =. 2005 , publisher =. doi:10.1103/PhysRevLett.94.197205 , url =

    2005 doi

  217. [235]

    Landscape of solutions in constraint satisfaction problems , author =. Phys. Rev. Lett. , year =. doi:110.1103/PhysRevLett.95.200202 , url =

  218. [236]

    Reconstruction on Trees and Spin Glass Transition , url =

    M. Reconstruction on Trees and Spin Glass Transition , url =. J. Stat. Phys. , number =. 2006 , bdsk-url-1 =. doi:10.1007/s10955-006-9162-3 , id =

    2006 doi

  219. [237]

    2017 , publisher =

    Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis , author =. 2017 , publisher =

    2017

  220. [238]

    Counting, Sampling and Integrating: Algorithms and Complexity by Mark Jerrum , volume =

    Aldous, David , year =. Counting, Sampling and Integrating: Algorithms and Complexity by Mark Jerrum , volume =. SIAM Review , doi =

  221. [239]

    Kempe Equivalence of Colorings , booktitle =

    Mohar, Bojan , editor =. Kempe Equivalence of Colorings , booktitle =. 2007 , publisher =. doi:10.1007/978-3-7643-7400-6_22 , url =

    2007 doi

  222. [240]

    Mohar, Bojan and Salas, Jes. A new. J. Phys. A: Math. Theor. , volume =

  223. [241]

    Mohar, Bojan and Salas, Jesús , title =. J. Stat. Mech.: Theory Exp. , abstract =. 2010 , publisher =. doi:10.1088/1742-5468/2010/05/P05016 , url =

    2010 doi

  224. [242]

    Approximate Counting, the

    Ankur Moitra , journal =. Approximate Counting, the. 2019 , doi =

    2019

  225. [243]

    Further algorithmic aspects of the local lemma , doi =

    Molloy, Michael and Reed, Bruce , booktitle =. Further algorithmic aspects of the local lemma , doi =

  226. [244]

    SODA , pages =

    Montanari, Andrea and Shah, Devavrat , title =. SODA , pages =. 2007 , isbn =

    2007

  227. [245]

    2008 , publisher =

    Andrea Montanari and Federico Ricci-Tersenghi and Guilhem Semerjian , title =. 2008 , publisher =. doi:10.1088/1742-5468/2008/04/P04004 , url =

    2008 doi

  228. [246]

    Montanari, Andrea and Restrepo, Ricardo and Tetali, Prasad , title =. SIAM J. Disc. Math. , volume =. 2011 , doi =

    2011

  229. [247]

    2025 , eprint =

    Sampling, Diffusions, and Stochastic Localization , author =. 2025 , eprint =

    2025

  230. [248]

    , booktitle =

    Moser, Robin A. , booktitle =. A constructive proof of the. doi:10.1145/1536414.1536462 , year =

  231. [249]

    and Tardos, G

    Moser, Robin A. and Tardos, G. A constructive proof of the general. J. doi:10.1145/1667053.1667060 , year =

  232. [250]

    and Yin, Yitong , title =

    Feng, Weiming and Vishnoi, Nisheeth K. and Yin, Yitong , title =. S. 2019 , mrclass =. doi:10.1145/3313276.3316365 , url =

    2019

  233. [251]

    Vadhan , title =

    Jack Murtagh and Omer Reingold and Aaron Sidford and Salil P. Vadhan , title =. Theory Comput. , doi =

  234. [252]

    Fast simulation of new coins from old , journal =

    Nacu,. Fast simulation of new coins from old , journal =. 2005 , number =

    2005

  235. [253]

    EUROCOMB , year =

    Vizing's edge-recoloring conjecture holds , author =. EUROCOMB , year =. doi:10.5817/CZ.MUNI.EUROCOMB23-102 , organization =

    doi

  236. [254]

    doi:10.2172/4390578 , journal =

    Equation of state calculations by fast computing machines , author =. doi:10.2172/4390578 , journal =

    doi

  237. [255]

    Infinite Number of Order Parameters for Spin-Glasses , author =. Phys. Rev. Lett. , volume =. 1979 , publisher =. doi:10.1103/PhysRevLett.43.1754 , url =

    1979 doi

  238. [256]

    Patel, Viresh and Regts, Guus , title =. SIAM J. Comput. , fjournal =. 2017 , number =. doi:10.1137/16M1101003 , url =

    2017 doi

  239. [257]

    Michigan Math

    Peters, Han and Regts, Guus , title =. Michigan Math. J. , fjournal =. 2019 , number =. doi:10.1307/mmj/1541667626 , url =

    2019

  240. [258]

    Vadhan , title =

    Edward Pyne and Salil P. Vadhan , title =. SOSA , doi =

  241. [259]

    and Wilson, David B

    Propp, James G. and Wilson, David B. , journal =. Exact sampling with coupled. doi:10.1002/(SICI)1098-2418(199608/09)9:1/2 number =

    doi

  242. [260]

    ICALP , pages =

    Guoliang Qiu and Yanheng Wang and Chihao Zhang , title =. ICALP , pages =

  243. [261]

    Inapproximability of counting independent sets in linear hypergraphs , journal =

    Guoliang Qiu and Jiaheng Wang , keywords =. Inapproximability of counting independent sets in linear hypergraphs , journal =. 2024 , issn =. doi:https://doi.org/10.1016/j.ipl.2023.106448 , url =

    2024

  244. [262]

    RANDOM , pages =

    Raab, Martin and Steger, Angelika , title =. RANDOM , pages =. 1998 , isbn =

    1998

  245. [263]

    , year = 2015, journal =

    Rhee, Chang-Han and Glynn, Peter W. , year = 2015, journal =. Unbiased. doi:10.1287/opre.2015.1404 , langid =

    2015

  246. [264]

    Servedio and Li

    Rocco A. Servedio and Li. Pseudorandomness for read- k. SODA , doi =

  247. [265]

    Absence of phase transition for antiferromagnetic. J. Stat. Phys. , author =. 1997 , pages =. doi:10.1007/BF02199113 , abstract =

    1997 doi

  248. [266]

    Ergodicity of the

    Salas, Jes. Ergodicity of the. J. Phys. A: Math. Theor. , volume =. 2022 , doi =

    2022

  249. [267]

    Arora, Sanjeev and Safra, Shmuel , title =. J. ACM , pages =. 1998 , issue_date =. doi:10.1145/273865.273901 , abstract =

    1998

  250. [268]

    Arora, Sanjeev and Lund, Carsten and Motwani, Rajeev and Sudan, Madhu and Szegedy, Mario , title =. J. ACM , pages =. 1998 , publisher =. doi:10.1145/278298.278306 , abstract =

    1998

  251. [269]

    and Laumann, Christopher R

    Sattath, Or and Morampudi, Siddhardh C. and Laumann, Christopher R. and Moessner, Roderich , title =. PNAS , volume =. 2016 , publisher =. doi:10.1073/pnas.1519833113 , url =

    2016 doi

  252. [270]

    , title =

    Schaefer, Thomas J. , title =. STOC , year =

  253. [271]

    and Sokal, Alan D

    Scott, Alexander D. and Sokal, Alan D. , journal =. The repulsive lattice gas, the independent-set polynomial, and the. 2005 , publisher =. doi:10.1007/s10955-004-2055-4 , url =

    2005 doi

  254. [272]

    , title =

    Shearer, James B. , title =. Combinatorica , fjournal =. 1985 , number =

    1985

  255. [273]

    doi:10.1007/s10955-014-0947-5 , adsurl =

    Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs , journal =. doi:10.1007/s10955-014-0947-5 , adsurl =

    doi

  256. [274]

    Information and Computation , volume =

    Approximate counting, uniform generation and rapidly mixing Markov chains , author =. Information and Computation , volume =. 1989 , publisher =

    1989

  257. [275]

    Computational Transition at the Uniqueness Threshold , year =

    Sly, Allan , booktitle =. Computational Transition at the Uniqueness Threshold , year =

  258. [276]

    Counting in two-spin models on d -regular graphs , author =. Ann. Probab. , volume =. 2014 , publisher =. doi:10.1214/13-AOP888 , url =

    2014 doi

  259. [277]

    A personal list of unsolved problems concerning lattice gases and antiferromagnetic

    Sokal, Alan D , journal =. A personal list of unsolved problems concerning lattice gases and antiferromagnetic. 2001 , publisher =

    2001

  260. [278]

    SODA , pages =

    Srinivasan, Aravind , title =. SODA , pages =. 2008 , mrclass =

    2008

  261. [279]

    2009 , number =

    Adaptive simulated annealing: a near-optimal connection between sampling and counting , journal =. 2009 , number =. doi:10.1145/1516512.1516520 , url =

    2009

  262. [280]

    The logarithmic

    Stroock, Daniel W and Zegarli. The logarithmic. Commun. Math. Phys , volume =. 1992 , publisher =

    1992

  263. [281]

    Takeharu Shiraga and Yukiko Yamauchi and Shuji Kijima and Masafumi Yamashita , title =. Theor. Comput. Sci. , doi =

  264. [282]

    doi:10.1137/16M1087667 , volume =

    Takeharu Shiraga and Yukiko Yamauchi and Shuji Kijima and Masafumi Yamashita , title =. doi:10.1137/16M1087667 , volume =

    doi

  265. [283]

    and Vigoda, Eric and Yang, Linji , title =

    Tetali, Prasad and Vera, Juan C. and Vigoda, Eric and Yang, Linji , title =. SODA , pages =. 2010 , isbn =

    2010

  266. [284]

    Spencer , title =

    Madhur Tulsiani and Scribe Kaustav Kundu and Michael Mitzenmacher and Eli Upfal and Joel H. Spencer , title =

  267. [285]

    Interactive proofs and the hardness of approximating cliques , year =

    Feige, Uriel and Goldwasser, Shafi and Lov\'. Interactive proofs and the hardness of approximating cliques , year =. J. ACM , month = mar, pages =. doi:10.1145/226643.226652 , abstract =

  268. [286]

    FOCS , pages =

    Vigoda, Eric , title =. FOCS , pages =. 1999 , isbn =

    1999

  269. [287]

    Perfectly sampling

    Vishesh Jain and Ashwin Sah and Mehtaab Sawhney , editor =. Perfectly sampling. 2021 , url =. doi:10.1145/3406325.3451012 , timestamp =

    2021

  270. [288]

    Vishesh Jain and Will Perkins and Ashwin Sah and Mehtaab Sawhney , title =

  271. [289]

    arXiv preprint arXiv:2102.08342 , title =

    Vishesh Jain and Huy Tuan Pham and Thuy-Duong Vuong , eprint =. arXiv preprint arXiv:2102.08342 , title =

    arXiv

  272. [290]

    FOCS , pages =

    Vishesh Jain and Huy Tuan Pham and Thuy-Duong Vuong , title =. FOCS , pages =. 2021 , doi =

    2021

  273. [291]

    Monte Carlo Method , publisher =

    Various techniques used in connection with random digits , author =. Monte Carlo Method , publisher =. 1951 , pages =

    1951

  274. [292]

    and Koteck\'y, Roman , journal =

    Wang, Jian-Sheng and Swendsen, Robert H. and Koteck\'y, Roman , journal =. Antiferromagnetic. 1989 , publisher =. doi:10.1103/PhysRevLett.63.109 , url =

    1989 doi

  275. [293]

    and Koteck\'y, Roman , journal =

    Wang, Jian-Sheng and Swendsen, Robert H. and Koteck\'y, Roman , journal =. Three-state antiferromagnetic. 1990 , publisher =. doi:10.1103/PhysRevB.42.2465 , url =

    1990 doi

  276. [294]

    FOCS , title =

    Wang, Chunyang and Yin, Yitong , author+an =. FOCS , title =. 2024 , volume =. doi:10.1109/FOCS61266.2024.00019 , url =

    2024

  277. [295]

    2024 , isbn =

    Wang, Yulin and Zhang, Chihao and Zhang, Zihan , title =. 2024 , isbn =. doi:10.1145/3618260.3649724 , booktitle =

    2024

  278. [296]

    Counting independent sets up to the tree threshold , year =

    Dror Weitz , booktitle =. Counting independent sets up to the tree threshold , year =

  279. [297]

    Mixing Times of

    David Bruce Wilson , journal =. Mixing Times of

  280. [298]

    SODA , pages =

    Yitong Yin and Chihao Zhang , title =. SODA , pages =. 2013 , url =. doi:10.1137/1.9781611973105.4 , timestamp =

    2013 doi

  281. [299]

    Dmitriy Zhuk , title =. J. 2020 , publisher =

    2020

Pith tools

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