![Algorithms and Complexity in Algebraic Geometry_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithms%20and%20Complexity%20in%20Algebraic%20Geometry_hi-res.jpg?h=450de763&itok=r3pqykMn)
Abstract
Minkowski's mixed volume is a generalization of the ordinary n-volume to n-tuples of convex bodies. According to Bernstein's Theorem, the number of non-zero isolated complex solutions of a system of n polynomials in n variables is at most n! times the mixed volume of the convex hull of the support of each polynomial.
This invariant plays therefore an important role in polynomial solving, and a related object (a mixed subdivision) can be used as a starting system for homotopy algorithms.
I will present a new algorithm for mixed volume and mixed subdivision computation. The basic idea behind this algorithm is to explore a finite number of toric varieties. Its complexity can be bounded in terms of certain mixed volumes. In case all of the polytopes are n-dimensional, this algorithm is output sensitive.