Application of random walks in algorithms (in geometry)

• Lovász, László; Simonovits, Miklós: The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), 346--354, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990.
• Lovász, L.; Simonovits, M. Random walks in a convex body and an improved volume algorithm. Random Structures Algorithms 4 (1993), no. 4, 359--412.
• L. Lovász, and M. Simonovits: On the randomized complexity of volume and diameter, {\it Proc. 33rd IEEE FOCS}, (1992) 482--491.
• Kannan, R.; Lovász, L.; Simonovits, M. Isoperimetric problems for convex bodies and a localization lemma. Discrete Comput. Geom. 13 (1995), no. 3-4, 541--559.
• Kannan, Ravi; Lovász, László; Simonovits, Miklós: Random walks and an $O^*(n\sp 5)$ volume algorithm for convex bodies. Random Structures Algorithms 11 (1997), no. 1, 1--50.

  ---

• A. Brieden, Gritzman, R. Kannan, V. Klee, L. Lov\'asz, M. Simonovits: Approximation of diameters: randomization doesn't help, Proc. 39th IEEE Symp. Found. Comput. Sci. (FOCS '98), 1998, pp. 244-251.
• A. Brieden, Gritzman, R. Kannan, V. Klee, L. Lov\'asz, M. Simonovits: Approximation of Radii and norm-maxima: no need to randomize, Accepted in Mathematika, 2000 (to appear in 2002)

Selected further papers in this topic

• Gyorgy Elekes (1986): A geometric inequality and the complexity of computing volume, Discrete and Computational Geometry, pp. 289--292.
• I. Bárány and Z. F\"uredi (1986): Computing the volume is difficult, Proc. of the 18th Annual ACM Symposium on Theory of Computing, pp. 442--447.
• Berndt~Carl (1985): Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces, {\it The Annales de l'Institute Fourier} {\bf 35}, pp. 79--118.
• Sinclair, Alistair; Jerrum, Mark Approximate counting, uniform generation and rapidly mixing Markov chains (extended abstract). Graph-theoretic concepts in computer science (Staffelstein, 1987), 134--148, Lecture Notes in Comput. Sci., 314, Springer, Berlin, 1988.
• Jerrum, Mark; Sinclair, Alistair Approximating the permanent. SIAM J. Comput. 18 (1989), no. 6, 1149--1178.
• Sinclair, Alistair; Jerrum, Mark Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput. 82 (1989), no. 1, 93--133.
• Dyer, Martin; Frieze, Alan, Computing the volume of convex bodies: a case where randomness provably helps. Probabilistic combinatorics and its applications (San Francisco, CA, 1991), 123--169, Proc. Sympos. Appl. Math., 44, Amer. Math. Soc., Providence, RI, 1991.
• Dyer, Martin; Frieze, Alan; Kannan, Ravi: A random polynomial-time algorithm for approximating the volume of convex bodies. J. Assoc. Comput. Mach. 38 (1991), no. 1, 1--17.
• Applegate-Kannan:
• Frieze, Alan; Kannan, Ravi, Log-Sobolev inequalities and sampling from log-concave distributions. Ann. Appl. Probab. 9 (1999), no. 1, 14--26.
• Chen, Fang; Lovász, László; Pak, Igor: Lifting Markov chains to speed up mixing. Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), 275--281 (electronic), ACM, New York, 1999.
• Lovász, László; Ravi Kannan: Faster mixing via average conductance. Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), 282--287 (electronic), ACM, New York, 1999.
• L. G. Khachiyan (1988): On the complexity of computing the volume of a polytope. {\it Izvestia Akad. Nauk SSSR, Engineering Cybernetics} {\bf 3}, pp. 216--217.
• László Lovász; Winkler, Peter Mixing times. Microsurveys in discrete probability (Princeton, NJ, 1997), 85--133, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 41, Amer. Math. Soc., Providence, RI, 1998.
• Lovász, László: Hit-and-run mixes fast. Math. Program. 86 (1999), no. 3, Ser. A, 443--461.
• L. Lovász-Santosh Vempala: ...

The basic book: