Title: On the Complexity of the Mixed Volume of Parallelograms
Speaker: Leonid Gurvits, CCNY
Date: Monday, February 23, 2015 11:00 am
Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
I will first review the only and inherently randomized poly-time algorithm to approximate the mixed volume $MV(K_1,...,K_n)$ of $n$ convex bodies $K_1,...,K_n$ in $R^n$ within the relative error $e^n$. If the affine dimensions of the $K_i$'s are at most 2 then the algorithm approximates within the relative error $(1 + sqrt{2})^n$. If the $K_i$'s are parallelograms then their mixed volume is essentially the exponential sum $sum_{S subset {1,...,n}} |det(A_{S})|$, where $A$ is some matrix and $A_{S}$ are its principal submatrices.
I will explain a few hardness and universality results that prohibit "natural" approaches and will describe a deterministic poly-time algorithm to compute the mixed volume of parallelograms within the relative error $2^n$.
Some open problems will be stated.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math