Counting independent sets up to the tree threshold
From MaRDI portal
Publication:2931378
DOI10.1145/1132516.1132538zbMath1301.68276OpenAlexW2004724832MaRDI QIDQ2931378
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
Graph theory (including graph drawing) in computer science (68R10) 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) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items
Spatial mixing and the connective constant: optimal bounds, \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, A Spectral Independence View on Hard Spheres via Block Dynamics, The topological strong spatial mixing property and new conditions for pressure approximation, Zero-freeness and approximation of real Boolean Holant problems, A Graph Polynomial for Independent Sets of Bipartite Graphs, The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs, Strong spatial mixing for repulsive point processes, An FPTAS for the hardcore model on random regular bipartite graphs, Zeros and approximations of holant polynomials on the complex plane, Correlation decay for hard spheres via Markov chains, Algorithmic Pirogov-Sinai theory, Total variation discrepancy of deterministic random walks for ergodic Markov chains, On the connection between interval size functions and path counting, Glauber dynamics for Ising models on random regular graphs: cut-off and metastability, Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing, The complexity of approximating bounded-degree Boolean \(\#\)CSP, The mean field traveling salesman and related problems, Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs, A dichotomy for bounded degree graph homomorphisms with nonnegative weights, What can be sampled locally?, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, Correlation decay and deterministic FPTAS for counting colorings of a graph, Exact thresholds for Ising-Gibbs samplers on general graphs, Approximating partition functions of the two-state spin system, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Computing the Partition Function of a Polynomial on the Boolean Cube, Replica symmetry of the minimum matching, Unnamed Item, Factor models on locally tree-like graphs, Analyticity for classical gasses via recursion, Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019, Improved mixing condition on the grid for counting and sampling independent sets, A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix, Inapproximability of the Independent Set Polynomial in the Complex Plane, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Majority dynamics on trees and the dynamic cavity method, Dismantlability, connectedness, and mixing in relational structures, Counting Constraint Satisfaction Problems., An SMB approach for pressure representation in amenable virtually orderable groups, The Ising partition function: zeros and deterministic approximation, Location of zeros for the partition function of the Ising model on bounded degree graphs, Approximation via Correlation Decay When Strong Spatial Mixing Fails, Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, A hard-core stochastic process with simultaneous births and deaths, A Faster FPTAS for #Knapsack, Algorithms for #BIS-Hard Problems on Expander Graphs, Faster exponential-time algorithms for approximately counting independent sets, Counting hypergraph matchings up to uniqueness threshold, A faster FPTAS for counting two-rowed contingency tables, Cayley trees do not determine the maximal zero-free locus of the independence polynomial, Independent sets in graphs, Approximating permanents and hafnians, Computing the partition function for graph homomorphisms, Approximately counting paths and cycles in a graph, Random sampling of colourings of sparse random graphs with a constant number of colours, Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees, Uniqueness thresholds on trees versus graphs, Lee-Yang theorems and the complexity of computing averages, Cutoff for General Spin Systems with Arbitrary Boundary Conditions, Strong spatial mixing in homomorphism spaces, Branching Process Approach for 2-Sat Thresholds, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, Approximating the volume of unions and intersections of high-dimensional geometric objects, On systematic scan for sampling H-colorings of the path, Rapid mixing of Gibbs sampling on graphs that are sparse on average, Unnamed Item, Unnamed Item, Exponential Time Complexity of Weighted Counting of Independent Sets, Zero-free regions of partition functions with applications to algorithms and graph limits, Sampling independent sets in the discrete torus, Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models, An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution, Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs, On a conjecture of Sokal concerning roots of the independence polynomial, Fisher zeros and correlation decay in the Ising model, On trees with real-rooted independence polynomial, Approximating the partition function of planar two-state spin systems, Phase Coexistence for the Hard-Core Model on ℤ2, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs, On the hardness of sampling independent sets beyond the tree threshold, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, Dismantlability, Connectedness, and Mixing in Relational Structures, Fisher Zeros and Correlation Decay in the Ising Model, Exact recovery in the Ising blockmodel, Counting Hypergraph Colorings in the Local Lemma Regime, Deterministic counting of graph colourings using sequences of subgraphs, Uniqueness of Gibbs measures for continuous hardcore models, 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, Sequential cavity method for computing free energy and surface pressure, Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Implementations and the independent set polynomial below the Shearer threshold, Unnamed Item, Strong spatial mixing of list coloring of graphs, Polymer dynamics via cliques: new conditions for approximations, Improved inapproximability results for counting independent sets in the hard-core model, Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree, Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction, Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, Absence of zeros implies strong spatial mixing, 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†, Approximately counting independent sets in bipartite graphs via graph containers, Correlation decay and the absence of zeros property of partition functions, Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \), Algorithms for hard-constraint point processes via discretization, Exact distributed sampling, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Approximation Algorithms for the Random Field Ising Model, Unnamed Item, Unnamed Item, Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial, Interactions of computational complexity theory and mathematics, Online Edge Coloring via Tree Recurrences and Correlation Decay, Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, Counting independent sets in graphs with bounded bipartite pathwidth, Gibbs rapidly samples colorings of \(G(n, d/n)\), Approximate Counting via Correlation Decay in Spin Systems, Gauges, loops, and polynomials for partition functions of graphical models, Dynamic Sampling from Graphical Models, Unnamed Item, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
