Faster mixing via average conductance

DOI10.1145/301250.301317MaRDI QIDQ2819555zbMATH OpenOpenAlexFDO

Authors R. Kannan, László Lovász

Publication date 29 September 2016

Published in Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/301250.301317

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational methods in Markov chains (60J22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Blocking Conductance and Mixing in Random Walks
• scientific article; zbMATH DE number 18982
• Random walks in a convex body and an improved volume algorithm
• The rapid mixing of random walks defined by an \(n\)-cube
• Hit-and-run mixes fast

Cited in

(25)

• Random walks on the random graph
• Mixing time bounds via bottleneck sequences
• A sharp log-Sobolev inequality for the multislice
• Log-Sobolev inequality for the multislice, with applications
• Approximating a sequence of observations by a simple process
• Evolving sets, mixing and heat kernel bounds
• Can Mixing Materials Make Electromagnetic Signals Travel Faster?
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• On the range of a random walk in a torus and random interlacements
• Mixing time of near-critical random graphs
• Recent progress on the random conductance model
• Vertex and edge expansion properties for rapid mixing
• Improved bounds for sampling contingency tables
• Fast mixing of Metropolized Hamiltonian Monte Carlo: benefits of multi-step gradients
• Multidimensional binary search for contextual decision-making
• A log-Sobolev inequality for the multislice, with applications
• Random walks on dynamic graphs: mixing times, hitting times, and return probabilities
• Blocking Conductance and Mixing in Random Walks
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• The mixing advantage is less than 2
• Efficient algorithms for the Potts model on small-set expanders
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• Large deviations for the isoperimetric constant in 2D percolation
• Sampling from convex sets with a cold start using multiscale decompositions
• Faster mixing and small bottlenecks

This page was built for publication: Faster mixing via average conductance

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