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)- 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
- On a conjecture of Sokal concerning roots of the independence polynomial
- Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures
- Perfect sampling from spatial mixing
- Fast algorithms at low temperatures via Markov chains†
- Sequential cavity method for computing free energy and surface pressure
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- Factor models on locally tree-like graphs
- Cutoff for general spin systems with arbitrary boundary conditions
- Zero-freeness and approximation of real Boolean Holant problems
- Independent sets in graphs
- Uniqueness thresholds on trees versus graphs
- Rapid mixing of Gibbs sampling on graphs that are sparse on average
- Approximation via Correlation Decay When Strong Spatial Mixing Fails
- On the connection between interval size functions and path counting
- scientific article; zbMATH DE number 7378644 (Why is no real title available?)
- Approximation Algorithms for the Random Field Ising Model
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
- Approximate counting via correlation decay in spin systems
- Counting constraint satisfaction problems
- Approximately counting independent sets in bipartite graphs via graph containers
- Location of zeros for the partition function of the Ising model on bounded degree graphs
- A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
- Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
- On the zeroes of hypergraph independence polynomials
- Quasipolynomial-time algorithms for Gibbs point processes
- Stochastic dynamics and the Polchinski equation: an introduction
- Approximating the volume of unions and intersections of high-dimensional geometric objects
- Counting independent sets using the Bethe approximation
- Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
- Interactions of computational complexity theory and mathematics
- Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \)
- Dynamic Sampling from Graphical Models
- Strong spatial mixing for repulsive point processes
- An FPTAS for the hardcore model on random regular bipartite graphs
- Correlation decay for hard spheres via Markov chains
- Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree
- The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
- Majority dynamics on trees and the dynamic cavity method
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)
