A simpler approach to randomized volume estimation

Martin Dyer

(University of Leeds)

The first polynomial time algorithm for estimating the volume of a convex body in high dimension was give by Dyer, Frieze and Kannan. Their technique relied on an eigenvalue estimation called "conductance" and isoperimetric inequalities for convex bodies. There have been great subsequent imrovements, but all have used essentially the same approach. We will show that, in the light of some of these improvements, a rather simpler method, called "coupling" can be used to prove the existence of polynomial time algorithms.

A review of the background, and an outline of the new approach, will be given. (No previous knowledge of the problem or the methods will be assumed.) This is joint work with Mark Jerrum and Russ Bubley.
Tuesday 21st November 1995, 14:30
Seminar Room 322
Department of Computer Science