An FPTAS for the hardcore model on random regular bipartite graphs
From MaRDI portal
Publication:2166750
DOI10.1016/j.tcs.2022.07.001OpenAlexW4284703375MaRDI QIDQ2166750
Jiabao Lin, Pinyan Lu, Chao Liao, Zhenyu Mao
Publication date: 25 August 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.07.001
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Combinatorics and complexity of partition functions
- Computing the partition function for graph homomorphisms with multiplicities
- An approximation trichotomy for Boolean \#CSP
- On the hardness of sampling independent sets beyond the tree threshold
- Cluster expansion for abstract polymer models
- Asymptotically optimal switching circuits
- 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
- Algorithms for #BIS-Hard Problems on Expander Graphs
- Approximating the Partition Function of the Ferromagnetic Potts Model
- An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Left and right convergence of graphs with bounded degree
- Counting independent sets in unbalanced bipartite graphs
- Algorithmic Pirogov-Sinai theory
- Improved Bounds for Randomly Sampling Colorings via Linear Programming
- Algorithms for #BIS-hard problems on expander graphs
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- The expressibility of functions on the boolean domain, with applications to counting CSPs
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Fast algorithms at low temperatures via Markov chains†
This page was built for publication: An FPTAS for the hardcore model on random regular bipartite graphs
