Approximate counting, uniform generation and rapidly mixing Markov chains

DOI10.1016/0890-5401(89)90067-9zbMath0668.05060OpenAlexW2072211488WikidataQ56386806 ScholiaQ56386806MaRDI QIDQ1117955

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90067-9

zbMATH Keywords

degree sequence counting problems labelled graphs generation problems simulation of ergodic Markov chains

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (05C99)

Related Items (only showing first 100 items - show all)

The generalized distance spectrum of a graph and applications ⋮ Completeness Results for Counting Problems with Easy Decision ⋮ A Note on the Conductance of the Binomial Random Intersection Graph ⋮ Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs ⋮ Graphs, Vectors, and Matrices ⋮ Equi-energy sampling does not converge rapidly on the mean-field Potts model with three colors close to the critical temperature ⋮ Sampling Edge Covers in 3-Regular Graphs ⋮ Unnamed Item ⋮ The Complexity of Computing the Random Priority Allocation Matrix ⋮ Complete Minors in Graphs Without Sparse Cuts ⋮ Improved bounds for the large-time behaviour of simulated annealing ⋮ Isoperimetry in Two-Dimensional Percolation ⋮ A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem ⋮ Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains ⋮ Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow ⋮ The cover time of a biased random walk on a random cubic graph ⋮ Fixed Precision MCMC Estimation by Median of Products of Averages ⋮ On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The vertex attack tolerance of complex networks ⋮ On Sampling Simple Paths in Planar Graphs According to Their Lengths ⋮ On the expansion of combinatorial polytopes ⋮ Mixing times of Markov chains for self‐organizing lists and biased permutations ⋮ A Markovian and Roe-algebraic approach to asymptotic expansion in measure ⋮ Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs ⋮ Time-optimal construction of overlay networks ⋮ Complexity results for MCMC derived from quantitative bounds ⋮ Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs ⋮ Approximately counting and sampling knowledge states ⋮ An invariance principle and a large deviation principle for the biased random walk on ⋮ Homomorphisms from the torus ⋮ Exact distributed sampling ⋮ Unnamed Item ⋮ Convergence of Gibbs sampling: coordinate hit-and-run mixes fast ⋮ Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian ⋮ Expander graphs and their applications ⋮ Geometric bounds on the fastest mixing Markov chain ⋮ Interactions of computational complexity theory and mathematics ⋮ Estimation of spectral gap for Markov chains ⋮ Unnamed Item ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs ⋮ A semidefinite bound for mixing rates of Markov chains ⋮ Characterizing optimal sampling of binary contingency tables via the configuration model ⋮ Testing Expansion in Bounded-Degree Graphs ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Estimate of exponential convergence rate in total variation by spectral gap ⋮ The mixing time of Glauber dynamics for coloring regular trees ⋮ Unnamed Item ⋮ Some results characterizing the finite time behaviour of the simulated annealing algorithm. ⋮ A new perspective on implementation by voting trees ⋮ A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant ⋮ Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks ⋮ Rapid mixing for lattice colourings with fewer colours ⋮ Expansion and Lack Thereof in Randomly Perturbed Graphs ⋮ Conductance bounds on the L² convergence rate of Metropolis algorithms on unbounded state spaces ⋮ Communities, Random Walks, and Social Sybil Defense ⋮ Sampling biased monotonic surfaces using exponential metrics ⋮ Finite-Time Behavior of Slowly Cooled Annealing Chains ⋮ High Dimensional Random Walks and Colorful Expansion ⋮ Deterministic counting of graph colourings using sequences of subgraphs ⋮ Optimal Construction of Edge-Disjoint Paths in Random Graphs ⋮ Time to Stationarity for a Continuous-Time Markov Chain ⋮ Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region ⋮ On the speed of random walks on graphs. ⋮ Random walks, totally unimodular matrices, and a randomised dual simplex algorithm ⋮ Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\). ⋮ Improving the characterization of P-stability for applications in network privacy ⋮ Geometric random edge ⋮ Spectral concentration and greedy \(k\)-clustering ⋮ The rapid mixing of random walks defined by an \(n\)-cube ⋮ On the cover time and mixing time of random geometric graphs ⋮ The local limit of the uniform spanning tree on dense graphs ⋮ Invasion percolation on Galton-Watson trees ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ Vertical perimeter versus horizontal perimeter ⋮ Simulated tempering and swapping on mean-field models ⋮ Random cluster dynamics for the Ising model is rapidly mixing ⋮ Exponential convergence for attractive reversible subcritical nearest particle systems ⋮ Semidefinite programming in combinatorial optimization ⋮ Agent-based randomized broadcasting in large networks ⋮ Half-regular factorizations of the complete bipartite graph ⋮ The mixing time of the giant component of a random graph ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Fault-tolerant aggregation: flow-updating meets mass-distribution ⋮ Markov chain convergence: From finite to infinite ⋮ Zeros and approximations of holant polynomials on the complex plane ⋮ Coupling, spectral gap and related topics. II ⋮ Algorithmic Pirogov-Sinai theory ⋮ Slow mixing of Markov chains using fault lines and fat contours ⋮ A sequential algorithm for generating random graphs ⋮ Sampling weighted perfect matchings on the square-octagon lattice ⋮ On the number of Eulerian orientations of a graph ⋮ Selection of relevant features and examples in machine learning ⋮ Spectral independence, coupling, and the spectral gap of the Glauber dynamics ⋮ Geometric bounds for convergence rates of averaging algorithms ⋮ Phase transition for the mixing time of the Glauber dynamics for coloring regular trees ⋮ Random walks on quasirandom graphs ⋮ Optimal scaling of random-walk Metropolis algorithms on general target distributions

Cites Work

This page was built for publication: Approximate counting, uniform generation and rapidly mixing Markov chains