Abstract:

   
   Universal Grobner bases have applications in solving systems of polynomial
   equations, in integer programming and combinatorial optimization, and more.
   
   In this talk I'll introduce these objects and describe our recent
   characterization (with Sturmfels, Berkeley) and polynomial time algorithm
   (with Babson-Thomas, Seattle) for universal bases of systems of
   polynomials with finite set of common zeros in fixed number of variables.
   
   On the way, I'll briefly overview our work on the complexity of
   the broadly expressive problem of partitioning a set of vectors
   so as to maximize an objective function which is convex on the
   sum of vectors in each part: suitable extensions of our geometric
   results on vector partitioning, carefully combined with algebraic
   ingredients, pave the way to our results on universal Grobner bases.