Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
From MaRDI portal
Publication:5875490
Cites work
- scientific article; zbMATH DE number 7204479 (Why is no real title available?)
- A complexity classification of spin systems with an external field
- Algorithmic Pirogov-Sinai theory
- Algorithms for #BIS-hard problems on expander graphs
- An FPTAS for counting proper four-colorings on cubic graphs
- An approximation trichotomy for Boolean \#CSP
- Cluster expansion for abstract polymer models
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Counting hypergraph colourings in the local lemma regime
- Counting independent sets up to the tree threshold
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- FPTAS for \#BIS with degree bounds on one side
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Improved FPTAS for multi-spin systems
- Improved bounds for sampling colorings
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- On Counting Independent Sets in Sparse Graphs
- On the hardness of sampling independent sets beyond the tree threshold
- Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
- Randomly coloring constant degree graphs
- Randomly coloring graphs of girth at least five
- Randomly coloring graphs with lower bounds on girth and maximum degree
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
- The relative complexity of approximate counting problems
Cited in
(13)- Homomorphisms from the torus
- Zeros and approximations of holant polynomials on the complex plane
- Polymer dynamics via cliques: new conditions for approximations
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures
- Independent sets in the hypercube revisited
- Fast algorithms for general spin systems on bipartite expanders
- Approximately counting independent sets in bipartite graphs via graph containers
- Fast mixing via polymers for random graphs with unbounded degree
- scientific article; zbMATH DE number 7650121 (Why is no real title available?)
- Algorithms for \#BIS-hard problems on expander graphs
- Counting solutions to random CNF formulas
This page was built for publication: Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875490)
