Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Hilbert Polytopes, Vector Partitions, and Polynomial Time Computation of Universal Bases of Systems of PolynomialsColloquium
|Speaker: ||Shmuel Onn, Technion - Israel Institute of Technology (currently visiting UCD)|
|Location: ||693 Kerr|
|Start time: ||Mon, May 6 2002, 4:10PM|
One of many features of the Universal basis of a system of polynomials is
that it allows solving the system by finding roots of univariate polynomials.
In this self contained talk I'll describe our work on Universal bases,
as well as overview and make use of our work on optimizing convex functions
over vector partitions, a problem of many applications, as follows:
(1) Our very recent discovery of a polynomial time algorithm for the
Universal basis of any system of polynomials having a finite zero
set in fixed dimension (with E.Babson & R.Thomas); here we use the
Hilbert polytope which we show is universal for the Hilbert scheme.
(2) A characterization of the Universal basis in the special case
of vanishing ideals of generic configurations (with B.Sturmfels).
(3) The complexity of convex vector partitioning (ongoing ISF-project,
works with various coauthors including N.Alon, F.Hwang, U.Rothblum).
I will conclude with several open questions and research directions
related to the best polynomial basis, coarsest Hilbert polytope, and
possible implications to discrete optimization and integer programming,
some of which are under investigation together with Jesus De Loera.