# 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

convex compact subsets in the Euclidean space

V

…, x

+…+λ

V(K

V(K

∂

V

+…λ

The mixed volume is one of the backbones of convexity theory.

After

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 (K

error e

K

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 (K

K

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.

**K**=(K_{1…}K_{n}) be a n-tuple ofconvex compact subsets in the Euclidean space

**R**^{n}, and let V (·) be the Euclidean volume in**R**^{n}. The Minkowski polynomialV

_{K}is defined as V_{K}(x_{1},…, x

_{n})= V (λ_{1}K_{1}+…+λ

_{n}K_{n}) and the mixed volumeV(K

_{1,…,}K_{n}) asV(K

_{1…}K

_{n}) =

∂

^{n}/ ∂λ

_{1…}∂λ

_{n}

V

_{K}(λ

_{1}K

_{1}

+…λ

_{n}K

_{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 (K

_{1,…,}K_{n}) with multiplicativeerror e

^{n}and with better rates if the affine dimensions of most of the setsK

_{i}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 (K

_{1,…,}K

_{n})). We prove the mixed volume analogues of the Van derWaerden 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:

52A39

Keywords: