APPLIED MATH SEMINAR

Name:  Hariharan Narayanan (University of Chicago)

Title:     Algorithmic applications of diffusion

When/where:  Friday, February 20, 10:30 AM, AKW 500

Abstract:        
The phenomenon of diffusion has been intensively studied in mathematics, physics, chemistry and biology. In this talk, we shall illustrate its use as an algorithmic tool.

One application that we shall describe is a new Markov chain for sampling polytopes and a randomized algorithm for linear programming. Both are based on an anisotropic diffusion process governed by a logarithmic barrier.

We shall also present an algorithm for approximating the surface area of a convex set based on the idea that the amount of heat diffusing out of a uniformly heated body in a small amount of time is proportional to its surface area.