Return to Colloquia & Seminar listing
Hilbert Polytopes, Vector Partitions, and Polynomial Time Computation of Universal Bases of Systems of Polynomials
Colloquium| 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.