Counting independent sets up to the tree threshold
From MaRDI portal
Publication:2931378
DOI10.1145/1132516.1132538zbMATH Open1301.68276OpenAlexW2004724832MaRDI QIDQ2931378FDOQ2931378
Authors: Dror Weitz 
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132538
Recommendations
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)
Cited In (only showing first 100 items - show all)
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- A graph polynomial for independent sets of bipartite graphs
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- Title not available (Why is that?)
- Deterministic counting of graph colourings using sequences of subgraphs
- The Ising partition function: zeros and deterministic approximation
- Spatial mixing and the connective constant: optimal bounds
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Approximately counting paths and cycles in a graph
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Counting hypergraph matchings up to uniqueness threshold
- Polymer dynamics via cliques: new conditions for approximations
- Uniqueness of Gibbs measures for continuous hardcore models
- Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Lee-Yang theorems and the complexity of computing averages
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Exact thresholds for Ising-Gibbs samplers on general graphs
- Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019
- On the hardness of sampling independent sets beyond the tree threshold
- A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
- Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
- Approximating the partition function of planar two-state spin systems
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- On trees with real-rooted independence polynomial
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Gibbs rapidly samples colorings of \(G(n, d/n)\)
- Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
- Computing the partition function for graph homomorphisms
- Replica symmetry of the minimum matching
- 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
- Cutoff for general spin systems with arbitrary boundary conditions
- Factor models on locally tree-like graphs
- 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
- Independent sets in graphs
- Rapid mixing of Gibbs sampling on graphs that are sparse on average
- Uniqueness thresholds on trees versus graphs
- Approximate counting via correlation decay in spin systems
- 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
- Dynamic Sampling from Graphical Models
- Approximating the volume of unions and intersections of high-dimensional geometric objects
- Strong spatial mixing of list coloring of graphs
- The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
- Majority dynamics on trees and the dynamic cavity method
- 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
- Exponential Time Complexity of Weighted Counting of Independent Sets
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- 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
- Glauber dynamics for Ising models on random regular graphs: cut-off and metastability
- Approximating permanents and hafnians
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- Correlation decay and the absence of zeros property of partition functions
- Sampling independent sets in the discrete torus
- Algorithmic Pirogov-Sinai theory
- The topological strong spatial mixing property and new conditions for pressure approximation
- Algorithms for \#BIS-hard problems on expander graphs
- Phase coexistence for the hard-core model on \(\mathbb{Z}^2\)
- Fisher zeros and correlation decay in the Ising model
- On the number of independent sets in a tree
- Approximation via correlation decay when strong spatial mixing fails
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- A faster FPTAS for counting two-rowed contingency tables
- Counting hypergraph colorings in the local lemma regime
- Computing the partition function of a polynomial on the Boolean cube
- Implementations and the independent set polynomial below the Shearer threshold
- 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
- Title not available (Why is that?)
- Exact recovery in the Ising blockmodel
- Dismantlability, connectedness, and mixing in relational structures
- Title not available (Why is that?)
- Zeros and approximations of holant polynomials on the complex plane
- Exact distributed sampling
- An SMB approach for pressure representation in amenable virtually orderable groups
- Faster exponential-time algorithms for approximately counting independent sets
- A hard-core stochastic process with simultaneous births and deaths
- Counting independent sets in amenable groups
- The complexity of approximating the matching polynomial in the complex plane
- Spectral independence via stability and applications to Holant-type problems
- Branching process approach for 2-SAT thresholds
- Absence of zeros implies strong spatial mixing
- Spatial mixing and the connective constant: optimal bounds
- 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
- Gauges, loops, and polynomials for partition functions of graphical models
- 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†
- Zero-freeness and approximation of real Boolean Holant 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)
