Algorithms for #BIS-Hard Problems on Expander Graphs
From MaRDI portal
Publication:3304735
DOI10.1137/19M1286669zbMath1451.68352MaRDI QIDQ3304735
Will Perkins, Peter Keevash, Matthew Jenssen
Publication date: 3 August 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (11)
Independent sets of a given size and structure in the hypercube ⋮ An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Zeros and approximations of holant polynomials on the complex plane ⋮ Fast mixing via polymers for random graphs with unbounded degree ⋮ Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence ⋮ Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Correlation decay and the absence of zeros property of partition functions ⋮ Sampling from the low temperature Potts model through a Markov chain on flows ⋮ Homomorphisms from the torus ⋮ Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Computing the permanent of (some) complex matrices
- The complexity of approximately counting stable matchings
- Counting in two-spin models on \(d\)-regular graphs
- Combinatorics and complexity of partition functions
- On the hardness of sampling independent sets beyond the tree threshold
- Cluster expansion for abstract polymer models
- Eigenvalues and expanders
- Asymptotically optimal switching circuits
- Random cluster dynamics for the Ising model is rapidly mixing
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- The relative complexity of approximate counting problems
- Algorithmic Pirogov-Sinai theory
- The replica symmetric solution for Potts models on \(d\)-regular graphs
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Counting independent sets up to the tree threshold
- FPTAS for #BIS with Degree Bounds on One Side
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- How to Play Unique Games on Expanders
- Polynomial-Time Approximation Algorithms for the Ising Model
- Explicit Concentrators from Generalized N-Gons
- Expander graphs and their applications
- A proof of alon's second eigenvalue conjecture
- Approximating the Partition Function of the Ferromagnetic Potts Model
- Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
- Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
- On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
- Counting independent sets in unbalanced bipartite graphs
- Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
- Weighted counting of solutions to sparse systems of equations
- Algorithms for #BIS-hard problems on expander graphs
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
This page was built for publication: Algorithms for #BIS-Hard Problems on Expander Graphs
