Spectral independence in high-dimensional expanders and applications to the hardcore model

DOI10.1137/20M1367696OpenAlexW3180870818MaRDI QIDQ5009783FDOQ5009783

Authors: Nima Anari, Kuikui Liu, 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

Recommendations

• Rapid mixing of hypergraph independent sets
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• Slow mixing of Glauber dynamics for the hard-core model on the hypercube
• Fast convergence of the Glauber dynamics for sampling independent sets
• Sampling independent sets in the discrete torus

zbMATH Keywords

Markov chain Monte Carloapproximate countingGlauber dynamicscorrelation decayhigh-dimensional expandersspectral independence

Mathematics Subject Classification ID

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

Cites Work

• On the hardness of sampling independent sets beyond the tree threshold
• Improved mixing condition on the grid for counting and sampling independent sets
• Applied analysis
• The Complexity of Enumeration and Reliability Problems
• Geometric bounds for eigenvalues of Markov chains
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Title not available (Why is that?)
• The computational complexity of two‐state spin systems
• 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
• Improved bounds on the phase transition for the hard-core model in 2-dimensions
• Computing the permanent of (some) complex matrices
• Approximating the Permanent
• The complexity of counting in sparse, regular, and planar graphs
• Phase coexistence and slow mixing for the hard-core model on \(\mathbb Z^{2}\)
• On Counting Independent Sets in Sparse Graphs
• Fast convergence of the Glauber dynamics for sampling independent sets
• Completely analytical interactions: Constructive description
• Title not available (Why is that?)
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Title not available (Why is that?)
• Counting in two-spin models on \(d\)-regular graphs
• Exact thresholds for Ising-Gibbs samplers on general graphs
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Correlation decay and deterministic FPTAS for counting list-colorings of a graph
• Title not available (Why is that?)
• On Markov Chains for Independent Sets
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Title not available (Why is that?)
• Matrix norms and rapid mixing for spin systems
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
• Combinatorics and complexity of partition functions
• Title not available (Why is that?)
• Approximating partition functions of the two-state spin system
• Title not available (Why is that?)
• On a conjecture of Sokal concerning roots of the independence polynomial
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Fisher zeros and correlation decay in the Ising model
• A note on the Glauber dynamics for sampling independent sets
• Phase coexistence for the hard-core model on \(\mathbb{Z}^2\)
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• High order random walks: beyond spectral gap
• High dimensional random walks and colorful expansion
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
• Swendsen-Wang dynamics for general graphs in the tree uniqueness region
• Computing the independence polynomial: from the tree threshold down to the roots
• Improved analysis of higher order random walks and applications
• Spatial mixing and the connective constant: optimal bounds
• Counting independent sets using the Bethe approximation
• Title not available (Why is that?)

Cited In (17)

• A spectral independence view on hard spheres via block dynamics
• Invariance of the essential spectra for perturbations with unbounded hard cores
• Polymer dynamics via cliques: new conditions for approximations
• Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
• Spectral independence via stability and applications to Holant-type problems
• Mixing of Markov chains for independent sets on chordal graphs with bounded separators
• A new correlation inequality for Ising models with external fields
• Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
• Interactions of computational complexity theory and mathematics
• Spectral independence, coupling, and the spectral gap of the Glauber dynamics
• Online Edge Coloring via Tree Recurrences and Correlation Decay
• Good quantum LDPC codes with linear time decoders
• Log concavity and concentration of Lipschitz functions on the Boolean hypercube
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Algorithms for hard-constraint point processes via discretization
• Boolean function analysis on high-dimensional expanders
• Spectral telescope: convergence rate bounds for random-scan Gibbs samplers based on a hierarchical structure

This page was built for publication: Spectral independence in high-dimensional expanders and applications to the hardcore model

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