[Colloquium] Santosh Vempala talk - Mon. 11/10 at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK

Speaker: Santosh Vempala
MIT
Speaker’s homepage: http://www-math.mit.edu/~vempala/

Time: 2:30pm
Date: Monday, November 10th
Place: TTI-C (1427 East 60th Street, Second Floor - Press Building)
*Refreshments provided*

Title: How to Walk in a Convex Body (Or Hit-and-Run Mixes Fast From Any Start)

Abstract: At first sight, getting around inside a convex body might seem to be 
an easy matter --- if a point X can be reached from another point Y, then in 
fact there is a straight line path. In high dimensions though, the perspective 
of the body from two different points could be very different. How then to 
quickly reach a random point in the body? 

In this talk, we will see that the random walk known as "hit-and-run" (pick a 
random direction, go to a random point on the chord it induces) mixes rapidly 
starting from any interior point. This is the first random walk known to have 
this property. The proof is based on a new geometric isoperimetric inequality. 
Time permitting, we will briefly survey applications to volume computation 
(with L. Lovasz) and optimization (with Adam Tau. Kalai). 
 
This is joint work with Laszlo Lovasz (Microsoft Research). 

Please contact Meridel with any questions: mtrimble at tti-c.org/4-9873

For information on future TTI Events, go to: http://www.tti-c.org/events.shtml