Faster mixing via average conductance

DOI10.1145/301250.301317zbMath1345.60078OpenAlexW1975813814MaRDI QIDQ2819555

László Lovász, Ravindran Kannan

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

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

Related Items

Log-Sobolev inequality for the multislice, with applications, Improved bounds for sampling contingency tables, Approximating a sequence of observations by a simple process, Faster mixing and small bottlenecks, Unnamed Item, 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, The evolution of the mixing rate of a simple random walk on the giant component of a random graph, Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile, Random walks on the random graph, Mixing time bounds via bottleneck sequences, Vertex and edge expansion properties for rapid mixing, Unnamed Item, Unnamed Item, Multidimensional Binary Search for Contextual Decision-Making, A sharp log-Sobolev inequality for the multislice, Evolving sets, mixing and heat kernel bounds