An FPTAS for the hardcore model on random regular bipartite graphs

DOI10.1016/J.TCS.2022.07.001MaRDI QIDQ2166750zbMATH OpenOpenAlexFDO

Authors Chao Liao, Jiabao Lin, Pinyan Lu, 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

zbMATH Keywords

coloringFPTAShardcore modelpolymer model

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• FPTAS for hardcore and Ising models on hypergraphs
• An entropy approach to the hard-core model on bipartite graphs
• scientific article; zbMATH DE number 753972
• Restricted Bipartite Graphs: Comparison and Hardness Results
• Bipartitioning of random graphs of fixed extensive valence
• An FPT algorithm for bipartite vertex splitting
• On the Hamiltonicity of random bipartite graphs
• Random procedures for dominating sets in bipartite graphs

Cites work

• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• A complexity classification of spin systems with an external field
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Algorithmic Pirogov-Sinai theory
• Algorithms for #BIS-hard problems on expander graphs
• Algorithms for \#BIS-hard problems on expander graphs
• An approximation trichotomy for Boolean \#CSP
• An FPTAS for counting proper four-colorings on cubic graphs
• Asymptotically optimal switching circuits
• Cluster expansion for abstract polymer models
• Combinatorics and complexity of partition functions
• Computing the partition function for graph homomorphisms with multiplicities
• Counting independent sets in unbalanced bipartite graphs
• Counting independent sets up to the tree threshold
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Fast algorithms at low temperatures via Markov chains†
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• FPTAS for \#BIS with degree bounds on one side
• scientific article; zbMATH DE number 1033851 (Why is no real title available?)
• scientific article; zbMATH DE number 7204479 (Why is no real title available?)
• Improved bounds for randomly sampling colorings via linear programming
• Improved bounds for sampling colorings
• Improved FPTAS for multi-spin systems
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Left and right convergence of graphs with bounded degree
• 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
• The expressibility of functions on the Boolean domain, with applications to counting CSPs
• The relative complexity of approximate counting problems

Cited in

(1)

• Rapid mixing via coupling independence for spin systems with unbounded degree

This page was built for publication: An FPTAS for the hardcore model on random regular bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2166750)