Polynomial Time Algorithms to Approximate Mixed Volumes Within a Simply Exponential Factor

Tuesday, April 17, 2007 - 1:30pm - 2:20pm
EE/CS 3-180
Leonid Gurvits (Los Alamos National Laboratory)
Let K =(K1…Kn) be a n-tuple of
convex compact subsets in the Euclidean space
Rn, and let V (·) be the Euclidean volume in
Rn . The Minkowski polynomial
VK is defined as VK(x1,
…, xn)= V (λ1K1
+…+λnKn) and the mixed volume
V(K1,…,Kn) as

V(K1…Kn) =
n / ∂λ1…∂λn

The mixed volume is one of the backbones of convexity theory.
After BKH theorem, the mixed volume( and its generalizations)
had become crucially important in computational algebraic geometry.

We present in this talk randomized and deterministic algorithms to
approximate the mixed volume of well-presented convex compact sets. Our main result is
a poly-time randomized algorithm which approximates
V (K1,…, Kn) with multiplicative
error en and with better rates if the affine dimensions of most of the sets
Ki are small.
Because of the famous Barany-Furedi lower bound, even such rate is not achievable by a poly-time deterministic oracle algorithm.

Our approach is based on the particular, geometric programming,
convex relaxation of log(V (K1,…,
Kn)). We prove the mixed volume analogues of the Van der
Waerden and the Schrijver/Valiant conjectures on the permanent. These results, interesting
on their own, allow to justify the above mentioned convex relaxation,
which is solved using the ellipsoid method and a randomized poly-time time
algorithm for the approximation of the volume of a convex set.
MSC Code: