Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We focus on the complexity of the problem of minimizing a polynomial function over integer points in a polyhedron. This problem is known to be NP-hard even fixed dimension two and degree four. Recently, Del Pia and Weismantel showed that for fixed dimension two and degree two, this problem can be solved in polynomial time. We continue this classification of problems that can be solved in polynomial time in fixed dimension by determining the complexity for minimizing cubic polynomials and homogeneous polynomials in dimension two over integer points in a polyhedron. Co-Authors: Alberto Del Pia (IBM Research), Robert Weismantel (ETH Zurich), and Kevin Zemmer (ETH Zurich)