DIMACS Discrete Math--Theory of Computing Seminar

Speaker: Alex Samorodnitsky, IAS, Princeton and DIMACS
Title: An algorithm for approximating mixed volumes and a combinatorial corollary.
Tuesday, December 7, 4:30-5:30, CoRe Building, Room 431, Rutgers University

Abstract:

We present a deterministic polynomial algorithm that computes the mixed discriminant of an $n$-tuple of positive semidefinite matrices to within a multiplicative factor of $2^{n^2}$.

As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of $n$ convex bodies in $\R^n$ to within a multiplicative factor of $2^{O(n^2)}$. This answers a question of Dyer, Gritzmann and Hufnagel.

A 'side benefit' is the following version of Rado's generalization of Hall's Marriage Theorem:

`` Let $A_1,...,A_n$ be subsets of $R^n$.

Assume, that there exists an $\epsilon > 0$, such that for any $k$-subset $S$ of $\{1...n\}$, and for any $k-1$-dimensional subspace $V$ of $R^n$, there is an element of $\cup_{i\in S} A_i$ of distance at least $\epsilon$ from $V$.

Assume also, that the vectors in $A_1,...,A_n$ are of length at most $L$.

Then there is a transversal $a_1 \in A_1$,...,$a_n \in A_n$ such that, for any $n-1$-dimensional subspace $U$ of $R^n$, there is an element of $\{a_1...a_n\}$ of distance at least $\delta$ from $U$, where $\delta$ can be taken as $$ L \cdot ( \epsilon / 2L )^{n^2}. $$

This is joint work with Leonid Gurvits.