Toward derandomizing Markov chain Monte Carlo
From MaRDI portal
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Analysis of algorithms (68W40)
Cites work
- A constructive proof of the general Lovász local lemma
- A general lower bound for mixing of single-site dynamics on graphs
- A geometric inequality and the complexity of computing volume
- A parallel algorithmic version of the local lemma
- A perfect sampler for hypergraph independent sets
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Algorithmic Pirogov-Sinai theory
- Approximate counting and sampling via local central limit theorems
- Approximate counting, the Lovász local lemma, and inference in graphical models
- Approximately counting independent sets in bipartite graphs via graph containers
- Approximation via Correlation Decay When Strong Spatial Mixing Fails
- Combinatorics and complexity of partition functions
- Computing the volume is difficult
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Correlation decay and partition function zeros: algorithms and phase transitions
- Counting hypergraph colorings in the local lemma regime
- Counting independent sets up to the tree threshold
- Deterministic approximation of random walks in small space
- Deterministic approximation of random walks via queries in graphs of unbounded size
- Deterministic counting Lov\'{a}sz local lemma beyond linear programming
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Deterministic random walks for rapidly mixing chains
- Deterministic random walks on regular trees
- DNF sparsification and a faster deterministic counting algorithm
- Efficient deterministic approximate counting for low-degree polynomial threshold functions
- Entropic independence: optimal mixing of down-up random walks
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- scientific article; zbMATH DE number 1775385 (Why is no real title available?)
- scientific article; zbMATH DE number 7650375 (Why is no real title available?)
- Improved bounds for perfect sampling of k-colorings in graphs
- Improved bounds for randomly colouring simple hypergraphs
- Improved bounds for randomly sampling colorings via linear programming
- Inapproximability of counting hypergraph colourings
- Inapproximability of counting independent sets in linear hypergraphs
- Left and right convergence of graphs with bounded degree
- Localization schemes: a framework for proving mixing bounds for Markov chains (extended abstract)
- Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Modified log-Sobolev inequalities for strongly log-concave distributions
- New constructive aspects of the Lovász local lemma
- Optimal mixing for two-state anti-ferromagnetic spin systems
- Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
- Path coupling using stopping times and counting independent sets and colorings in hypergraphs
- Perfect sampling from spatial mixing
- Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
- Perfect sampling using bounding chains.
- Perfectly sampling k ≥ (8/3 + o (1))Δ-colorings in graphs
- Polynomial-Time Approximation Algorithms for the Ising Model
- Pseudorandomness for read-k DNF formulas
- Random generation of combinatorial structures from a uniform distribution
- Randomly coloring simple hypergraphs
- Rapid mixing of Glauber dynamics up to uniqueness via contraction
- Rapid mixing of Glauber dynamics via spectral independence for all degrees
- Rapid mixing of hypergraph independent sets
- Sampling constraint satisfaction solutions in the local lemma regime
- Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
- Simulating a Random Walk with Constant Error
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Stopping Times, Metrics and Approximate Counting
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- Towards derandomising Markov chain Monte Carlo
- Towards the sampling Lovász local lemma
This page was built for publication: Toward derandomizing Markov chain Monte Carlo
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6967848)
