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

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, Computing elastic moduli of two-dimensional random networks of rigid and nonrigid bonds by simulated annealing, Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point, Mixing time of near-critical random graphs, Fast uniform generation of regular graphs, Complexity and approximability of the cover polynomial, Sampling online social networks by random walk with indirect jumps, On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries, Every ``lower psi-mixing Markov chain is ``interlaced rho-mixing, Multi-way dual Cheeger constants and spectral bounds of graphs, Optimal scaling for various Metropolis-Hastings algorithms., Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions, Characterization of equilibrium measures for critical reversible nearest particle systems, Metric uniformization and spectral bounds for graphs, On the conductance of order Markov chains, Counting linear extensions, Self-testing algorithms for self-avoiding walks, Analyzing Glauber dynamics by comparison of Markov chains, Nash inequalities for finite Markov chains, Fast mixing of Metropolis-Hastings with unimodal targets, On sensitivity of mixing times and cutoff, Thermalization time bounds for Pauli stabilizer Hamiltonians, Soft memberships for spectral clustering, with application to permeable language distinction, Laplace eigenvalues of graphs---a survey, Approximating the permanent of graphs with large factors, A faster exact-counting protocol for anonymous dynamic networks, Estimating the spectral gap of a trace-class Markov operator, Glauber dynamics for the mean-field Potts model, Simple bounds on the convergence rate of an ergodic Markov chain, The small world effect on the coalescing time of random walks, Spectra of lifted Ramanujan graphs, Systematic scan for sampling colorings, Cutoff for random walk on dynamical Erdős-Rényi graph, Mixing Times of Markov Chains of 2-Orientations, Sampling and Counting 3-Orientations of Planar Triangulations, The spectra of multiplicative attribute graphs, Asymptotic optimality of isoperimetric constants, A random polynomial time algorithm for well-routing convex bodies, Expanding and forwarding, The invisible hand of Laplace: the role of market structure in price convergence and oscillation, Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids, What do we know about the Metropolis algorithm?, Sampling Eulerian orientations of triangular lattice graphs, Discrepancy and eigenvalues of Cayley graphs, Convergence complexity analysis of Albert and Chib's algorithm for Bayesian probit regression, Bounds on the cover time, Integrating and Sampling Cuts in Bounded Treewidth Graphs, Expander properties and the cover time of random intersection graphs, Rapid Mixing and Markov Bases, Optimization problems for weighted graphs and related correlation estimates, A multiscale environment for learning by diffusion, Consistent estimation of the spectrum of trace class data augmentation algorithms, A new characterization of \(\mathcal{V} \)-posets, Log-Sobolev inequalities and sampling from log-concave distributions, The spectral gap of the REM under Metropolis dynamics, Discrete quantum walks hit exponentially faster, Faster random generation of linear extensions, Finite approximations to the critical reversible nearest particle system, On hyperboundedness and spectrum of Markov operators, Simple permutations mix well, Expansion in supercritical random subgraphs of the hypercube and its consequences, Efficient simulated annealing on fractal energy landscapes, On efficient randomized algorithms for finding the PageRank vector, Mixing times for the Swapping Algorithm on the Blume-Emery-Griffiths model, Dynamic averaging load balancing on cycles

Cites Work