Seminario Interdipartimentale di Algoritmica  

Monday, May 23, 2005, 12:00 noon
How to Compute the Volume in High Dimension?
Miklos Simonovits, Alfred Renyi Mathematical Institute, Budapest

DI - Department of Computer Science
Seminar Room, third floor

In some areas of theoretical computer science we feel that randomized algorithms are better and in some others we can prove that they are more efficient than deterministic ones. Approximating the volume of a convex n-dimensional body, given by an oracle is one of the areas where this difference can be proved. In general, if we use a deterministic algorithm to approximate the volume, it requires exponentially many oracle questions in terms of n as n goes to infinity. Dyer, Frieze and Kannan gave a randomized polynomial approximation algorithm for the volume of a convex body K, in the n-dimensional euclidean space R^n given by a membership oracle. The above algorithm was improved in a sequence of papers. The area is full of deep and interesting problems and results. The lecture gives an introduction to this field and also a survey.