Fast algorithms for general spin systems on bipartite expanders

DOI10.4230/LIPICS.MFCS.2020.37MaRDI QIDQ5089204zbMATH OpenFDO

Authors

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2020.37

zbMATH Keywords

approximate countingbipartite expandersspin systems

Mathematics Subject Classification ID

Expander graphs (05C48) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Fast algorithms for general spin systems on bipartite expanders
• Algorithms for \#BIS-hard problems on expander graphs
• Algorithms for #BIS-hard problems on expander graphs
• Counting in two-spin models on \(d\)-regular graphs
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

Cites work

• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Algorithmic Pirogov-Sinai theory
• Algorithms for #BIS-hard problems on expander graphs
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• Counting in two-spin models on \(d\)-regular graphs
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Counting independent sets in unbalanced bipartite graphs
• Eigenvalues and expansion of regular graphs
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Expander graphs and their applications
• Explicit Concentrators from Generalized N-Gons
• Explicit construction of linear sized tolerant networks
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 7650108 (Why is no real title available?)
• Interlacing eigenvalues and graphs
• Large incidence-free sets in geometries
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• The complexity of partition functions
• The relative complexity of approximate counting problems

Cited in

(6)

• Fast mixing via polymers for random graphs with unbounded degree
• Algorithms for \#BIS-hard problems on expander graphs
• Fast algorithms for general spin systems on bipartite expanders
• Approximately counting independent sets in bipartite graphs via graph containers
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• A refined graph container lemma and applications to the hard-core model on bipartite expanders

This page was built for publication: Fast algorithms for general spin systems on bipartite expanders

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