Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
From MaRDI portal
Publication:5875490
DOI10.4230/LIPICS.APPROX-RANDOM.2019.34OpenAlexW2979276937MaRDI QIDQ5875490FDOQ5875490
Authors: Chao Liao, Jiabao Lin, Pinyan Lu, Zhenyu Mao 
Publication date: 3 February 2023
Full work available at URL: https://arxiv.org/abs/1903.07531
Cites Work
- On the hardness of sampling independent sets beyond the tree threshold
- The relative complexity of approximate counting problems
- Cluster expansion for abstract polymer models
- Counting independent sets up to the tree threshold
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- An approximation trichotomy for Boolean \#CSP
- Improved bounds for sampling colorings
- 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
- On Counting Independent Sets in Sparse Graphs
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- A complexity classification of spin systems with an external field
- Randomly coloring graphs with lower bounds on girth and maximum degree
- Randomly coloring constant degree graphs
- Improved FPTAS for multi-spin systems
- An FPTAS for counting proper four-colorings on cubic graphs
- Randomly coloring graphs of girth at least five
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
- Algorithmic Pirogov-Sinai theory
- Algorithms for #BIS-hard problems on expander graphs
- FPTAS for \#BIS with degree bounds on one side
- Title not available (Why is that?)
- Counting hypergraph colourings in the local lemma regime
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
- Title not available (Why is that?)
- 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)
