Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model

DOI10.1137/20M1367696OpenAlexW3180870818MaRDI QIDQ5009783

Kuikui Liu, Nima Anari, Shayan Oveis Gharan

Publication date: 6 August 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.00303

zbMATH Keywords

Markov chain Monte CarloGlauber dynamicsapproximate countingcorrelation decayhigh-dimensional expandersspectral independence

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, A Spectral Independence View on Hard Spheres via Block Dynamics, Spectral independence, coupling, and the spectral gap of the Glauber dynamics, A new correlation inequality for Ising models with external fields, Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields, Algorithms for hard-constraint point processes via discretization, Spectral telescope: convergence rate bounds for random-scan Gibbs samplers based on a hierarchical structure, Interactions of computational complexity theory and mathematics, Online Edge Coloring via Tree Recurrences and Correlation Decay, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), Mixing of Markov chains for independent sets on chordal graphs with bounded separators, Log concavity and concentration of Lipschitz functions on the Boolean hypercube, Polymer dynamics via cliques: new conditions for approximations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the permanent of (some) complex matrices
• Counting in two-spin models on \(d\)-regular graphs
• Combinatorics and complexity of partition functions
• Geometric bounds for eigenvalues of Markov chains
• Matrix norms and rapid mixing for spin systems
• On the hardness of sampling independent sets beyond the tree threshold
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• A note on the Glauber dynamics for sampling independent sets
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
• Completely analytical interactions: Constructive description
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Approximating partition functions of the two-state spin system
• Improved mixing condition on the grid for counting and sampling independent sets
• High order random walks: beyond spectral gap
• On a conjecture of Sokal concerning roots of the independence polynomial
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Phase Coexistence and Slow Mixing for the Hard-Core Model on ℤ2
• Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• Counting Independent Sets Using the Bethe Approximation
• On Counting Independent Sets in Sparse Graphs
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Approximating the Permanent
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• The Complexity of Enumeration and Reliability Problems
• The computational complexity of two‐state spin systems
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• High Dimensional Random Walks and Colorful Expansion
• Fast convergence of the Glauber dynamics for sampling independent sets
• On Markov Chains for Independent Sets
• Swendsen‐Wang dynamics for general graphs in the tree uniqueness region
• Improved analysis of higher order random walks and applications
• Fisher zeros and correlation decay in the Ising model
• Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
• Phase Coexistence for the Hard-Core Model on ℤ²
• Spatial mixing and the connective constant: Optimal bounds
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Prescribing a System of Random Variables by Conditional Distributions
• Correlation Decay up to Uniqueness in Spin Systems
• Approximate Counting via Correlation Decay in Spin Systems
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion