Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We provide a polynomial time algorithm for computing the Universal Groebner basis of any system of polynomials having a finite solution set in fixed number of variables. An important role is played by a certain matroid polytope we associate with each polynomial ideal. Introducing the {\em Hilbert polytope} $H^d_n$ and showing that it simultaneously refines the matroid polytope of any such system in $d$ variables having at most $n$ solutions, we show our algorithm makes use of $O(n^{2d+1}(log n)^{(2d-1)(d-1)})$ arithmetic operations.