Counting independent sets up to the tree threshold
From MaRDI portal
Publication:2931378
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Classical equilibrium statistical mechanics (general) (82B05) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)
Recommendations
Cited in
(only showing first 100 items - show all)- Online Edge Coloring via Tree Recurrences and Correlation Decay
- Computing the independence polynomial: from the tree threshold down to the roots
- Strong spatial mixing of list coloring of graphs
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Strong spatial mixing in homomorphism spaces
- Approximating partition functions of the two-state spin system
- scientific article; zbMATH DE number 7650108 (Why is no real title available?)
- The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
- Exponential Time Complexity of Weighted Counting of Independent Sets
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- Finitary codings for spatial mixing Markov random fields
- An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- On systematic scan for sampling \(H\)-colorings of the path
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- Glauber dynamics for Ising models on random regular graphs: cut-off and metastability
- Approximating permanents and hafnians
- Sampling independent sets in the discrete torus
- Correlation decay and the absence of zeros property of partition functions
- Learning loosely connected Markov random fields
- Potential-weighted connective constants and uniqueness of Gibbs measures
- Algorithmic Pirogov-Sinai theory
- What can be sampled locally?
- Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
- Inapproximability of the independent set polynomial in the complex plane
- Analyticity for classical gasses via recursion
- The topological strong spatial mixing property and new conditions for pressure approximation
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- Counting independent sets in graphs with bounded bipartite pathwidth
- Complexity theory. Abstracts from the workshop held June 2--7, 2024
- Algorithms for \#BIS-hard problems on expander graphs
- Phase coexistence for the hard-core model on \(\mathbb{Z}^2\)
- A faster FPTAS for \#Knapsack
- Fisher zeros and correlation decay in the Ising model
- On the number of independent sets in a tree
- Algorithms for hard-constraint point processes via discretization
- Fisher Zeros and Correlation Decay in the Ising Model
- Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Approximation via correlation decay when strong spatial mixing fails
- A faster FPTAS for counting two-rowed contingency tables
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Implementations and the independent set polynomial below the Shearer threshold
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- Counting hypergraph colorings in the local lemma regime
- Computing the partition function of a polynomial on the Boolean cube
- A graph polynomial for independent sets of bipartite graphs
- scientific article; zbMATH DE number 1559584 (Why is no real title available?)
- Dismantlability, Connectedness, and Mixing in Relational Structures
- Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
- A spectral independence view on hard spheres via block dynamics
- The Ising partition function: zeros and deterministic approximation
- scientific article; zbMATH DE number 7650115 (Why is no real title available?)
- Deterministic counting of graph colourings using sequences of subgraphs
- Exact recovery in the Ising blockmodel
- Approximately counting paths and cycles in a graph
- Spatial mixing and the connective constant: optimal bounds
- Dismantlability, connectedness, and mixing in relational structures
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Zeros and approximations of holant polynomials on the complex plane
- scientific article; zbMATH DE number 7559110 (Why is no real title available?)
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Counting hypergraph matchings up to uniqueness threshold
- Polymer dynamics via cliques: new conditions for approximations
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Uniqueness of Gibbs measures for continuous hardcore models
- An SMB approach for pressure representation in amenable virtually orderable groups
- Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
- Exact distributed sampling
- Lee-Yang theorems and the complexity of computing averages
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Zero-free regions of partition functions with applications to algorithms and graph limits
- On the hardness of sampling independent sets beyond the tree threshold
- Exact thresholds for Ising-Gibbs samplers on general graphs
- Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019
- Faster exponential-time algorithms for approximately counting independent sets
- Approximating the partition function of planar two-state spin systems
- A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
- A hard-core stochastic process with simultaneous births and deaths
- On trees with real-rooted independence polynomial
- Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
- Counting independent sets in amenable groups
- The complexity of approximating the matching polynomial in the complex plane
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- Branching process approach for 2-SAT thresholds
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Cayley trees do not determine the maximal zero-free locus of the independence polynomial
- Mixing of Markov chains for independent sets on chordal graphs with bounded separators
- Spectral independence via stability and applications to Holant-type problems
- Spatial mixing and the connective constant: optimal bounds
- Replica symmetry of the minimum matching
- Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
- Computing the partition function for graph homomorphisms
- Absence of zeros implies strong spatial mixing
- Gibbs rapidly samples colorings of \(G(n, d/n)\)
- Gauges, loops, and polynomials for partition functions of graphical models
- Random sampling of colourings of sparse random graphs with a constant number of colours
- The mean field traveling salesman and related problems
This page was built for publication: Counting independent sets up to the tree threshold
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931378)
