Fast sampling via spectral independence beyond bounded-degree graphs
From MaRDI portal
Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)
Cites work
- Approximating the Permanent
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Block factorization of the relative entropy via spatial mixing
- Computational transition at the uniqueness threshold
- Correlation decay up to uniqueness in spin systems
- Counting independent sets up to the tree threshold
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Entropic independence: optimal mixing of down-up random walks
- Exact thresholds for Ising-Gibbs samplers on general graphs
- Glauber dynamics on trees and hyperbolic graphs
- High dimensional expanders imply agreement expanders
- High dimensional random walks and colorful expansion
- High order random walks: beyond spectral gap
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- scientific article; zbMATH DE number 7768381 (Why is no real title available?)
- Improved analysis of higher order random walks and applications
- Improved inapproximability results for counting independent sets in the hard-core model
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
- Localization schemes: a framework for proving mixing bounds for Markov chains (extended abstract)
- MCMC sampling colourings and independent sets of \(G(n, d/n)\) near uniqueness threshold
- On a conjecture of Sokal concerning roots of the independence polynomial
- On the mixing time of Glauber dynamics for the hard-core and related models on G(n,d/n)
- Optimal mixing for two-state anti-ferromagnetic spin systems
- Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
- Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
- Rapid mixing of Glauber dynamics via spectral independence for all degrees
- Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
- Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
- Sampling random colorings of sparse random graphs
- Spatial mixing and approximation algorithms for graphs with bounded connective constant
- Spatial mixing and the connective constant: optimal bounds
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- The Complexity of Approximating the Matching Polynomial in the Complex Plane
- The computational hardness of counting in two-spin models on d-regular graphs
- The evolution of the mixing rate of a simple random walk on the giant component of a random graph
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
Cited in
(4)
This page was built for publication: Fast sampling via spectral independence beyond bounded-degree graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023572)
