Random Walks and Geometric Algorithms
Santosh Vempala, Department of Mathematics, MIT

Abstract:
Random walks have intrigued us for a long time. In recent years, they have also played a crucial role in the discovery of polynomial-time algorithms. This talk will focus on geometric random walks, illustrate their applicability via a simple algorithm for optimization, and then move to the question of what distributions in space can be sampled efficiently by a random walk. Along the way, we will see some engaging ways to walk randomly and highlight the properties of a rather remarkable one, called "hit-and-run".

This is joint work with D. Bertsimas and L. Lovasz.

Host: Avrim Blum