Faster mixing via average conductance

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Faster mixing via average conductance

Full text

Pdf (402 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 282 - 287

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

László Lovász	Department of Computer Science, Yale University
Ravi Kannan	Department of Computer Science, Yale University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 39, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301317 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AF	D. J. Aldous and J. Fill (1998) : Reversible Markov Chains and Random Walks on Graphs (book), t~o appear. U RL for draft at ht t,p://www, s~ at.. Berkeley. ed u / users/aldous/boo k. html
	CL	F. Chen ~nd L. Lov~sz (unpublished)
	DS	P. Diaconis and L. Saloff-Coste: Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probability 6 (1996), 695-750.
	DF	M. Dyer and A. Frieze (1992): Comparing the volume of convex bodies: ~ case where randomness provably l~elps, in: Probabilistic Combinatorics and Its Applications (ed. B~la BoI!ob~s), Proceedings of Symposi~ in Applied M~them~tics, Vol. 44, 123-170.
	DFK	M. Dyer , A. Frieze, A random polynomial time algorithm for approximating the volume of convex bodies, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.375-381, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73043]
	FK	A. M. Frieze a~nd R. Kannan: Log-Sobolev ineqaaJJties and sampling from log-conc~ve distributions, t,o appear in the AnnaJs of Applied Probability.
	JS	Mark Jerrum , Alistair Sinclair, Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.235-244, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62234]
	KLS	Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
	KLS2	R. Kannan, L. Lov~sz and M. Simonovi~s (1995): Isoperimetric problems for convex bodies and a localization lemma, J. Discr. Gomput. Geom. 13 541-559.
	LS	L. Lov~z and M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures and Alg. 4 (1993), 359-412.
	LS1	L. Lov~z and M. Simonovits (1990): Mixing rate of Markov chains, an isoperimet~ric inequality, and computing the volume. Prec. $Ist Annual $~tmp. on Found. o{ Computer Science, IEEE Computer Soc., 346-355.
	LW1	László Lovász , Peter Winkler, Efficient stopping rules for Markov chains, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.76-82, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225086]
	LW2	L. Lov~sz and P. Winlder, Mixing times, in: Microsurveys in Discrete Probability (ed. D. Aldous and J. Propp), DIMACS Series in Discr. Math. and Theor. Comp. Sci., 41, 85-133.

CITED BY 9

	Andris Ambainis , Eric Bach , Ashwin Nayak , Ashvin Vishwanath , John Watrous, One-dimensional quantum walks, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.37-49, July 2001, Hersonissos, Greece
	Ravi Montenegro , Jung-Bae Son, Edge isoperimetry and rapid mixing on matroids and geometric Markov chains, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.704-711, July 2001, Hersonissos, Greece
	Igor Pak, Mixing time and long paths in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.321-328, January 06-08, 2002, San Francisco, California
	László Lovász , Santosh Vempala, Hit-and-run from a corner, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Dimitris Bertsimas , Santosh Vempala, Solving convex programs by random walks, Journal of the ACM (JACM), v.51 n.4, p.540-556, July 2004
	Ben J. Morris, Improved bounds for sampling contingency tables, Random Structures & Algorithms, v.21 n.2, p.135-146, September 2002
	R. Montenegro , P. Tetali, Mathematical aspects of mixing times in Markov chains, Foundations and Trends® in Theoretical Computer Science, v.1 n.3, p.237-354, May 2006
	László Lovász , Santosh Vempala, The geometry of logconcave functions and sampling algorithms, Random Structures & Algorithms, v.30 n.3, p.307-358, May 2007
	N. Fountoulakis , B. A. Reed, The evolution of the mixing rate of a simple random walk on the giant component of a random graph, Random Structures & Algorithms, v.33 n.1, p.68-86, August 2008