Dynamic Sampling from Graphical Models
From MaRDI portal
Publication:5858642
DOI10.1137/20M1315099OpenAlexW3136868327MaRDI QIDQ5858642
Nisheeth K. Vishnoi, Weiming Feng, Yitong Yin
Publication date: 14 April 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1315099
Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ising models on locally tree-like graphs
- Random generation of combinatorial structures from a uniform distribution
- Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
- Random cluster dynamics for the Ising model is rapidly mixing
- Perfect sampling using bounding chains.
- The random-cluster model on a homogeneous tree
- Exact thresholds for Ising-Gibbs samplers on general graphs
- What can be sampled locally?
- A general lower bound for mixing of single-site dynamics on graphs
- Improved bounds for sampling colorings
- Counting independent sets up to the tree threshold
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Polynomial-Time Approximation Algorithms for the Ising Model
- Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
- Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
- A constructive proof of the general lovász local lemma
- Graphical Models, Exponential Families, and Variational Inference
- Information, Physics, and Computation
- 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
- Fast convergence of the Glauber dynamics for sampling independent sets
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- On Markov Chains for Independent Sets
- An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles
- Real stable polynomials and matroids: optimization and counting
- New bounds for the Moser‐Tardos distribution
- Tight bounds for popping algorithms
- The Moser--Tardos Framework with Partial Resampling
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models
- Uniform Sampling Through the Lovász Local Lemma
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- New Constructive Aspects of the Lovász Local Lemma
- Strong Spatial Mixing with Fewer Colors for Lattice Graphs
This page was built for publication: Dynamic Sampling from Graphical Models
