Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
From MaRDI portal
Publication:5875490
DOI10.4230/LIPIcs.APPROX-RANDOM.2019.34OpenAlexW2979276937MaRDI QIDQ5875490
Jiabao Lin, Pinyan Lu, Chao Liao, Zhenyu Mao
Publication date: 3 February 2023
Full work available at URL: https://arxiv.org/abs/1903.07531
Related Items
Zeros and approximations of holant polynomials on the complex plane, Fast mixing via polymers for random graphs with unbounded degree, Counting Solutions to Random CNF Formulas, Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures, Approximately counting independent sets in bipartite graphs via graph containers, Homomorphisms from the torus, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Unnamed Item, Independent sets in the hypercube revisited, Algorithms for #BIS-Hard Problems on Expander Graphs, Unnamed Item, Polymer dynamics via cliques: new conditions for approximations
Cites Work
- Unnamed Item
- Unnamed Item
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- An approximation trichotomy for Boolean \#CSP
- On the hardness of sampling independent sets beyond the tree threshold
- Cluster expansion for abstract polymer models
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- The relative complexity of approximate counting problems
- Improved bounds for sampling colorings
- Improved FPTAS for Multi-spin Systems
- Randomly coloring constant degree graphs
- Counting independent sets up to the tree threshold
- FPTAS for #BIS with Degree Bounds on One Side
- A complexity classification of spin systems with an external field
- On Counting Independent Sets in Sparse Graphs
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Randomly coloring graphs of girth at least five
- Approximating the Partition Function of the Ferromagnetic Potts Model
- Randomly coloring graphs with lower bounds on girth and maximum degree
- An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
- The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
- Algorithmic Pirogov-Sinai theory
- Counting hypergraph colourings in the local lemma regime
- Algorithms for #BIS-hard problems on expander graphs
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
