USI - Email

Archive / INF Seminars 2018-2025 / INF_2025_09_25_LucasSlot

USI - Email

	The Computational Complexity of Convex Polynomial Optimization

Thursday

25.09

USI Campus EST, Room D1.14

15:30 - 16:30


	Lucas Slot ETH Zürich

Abstract: We consider the computational complexity of minimizing a convex polynomial over Rⁿ, or over a convex polyhedron. While this problem appears amenable to standard optimization algorithms such as the ellipsoid method or gradient descent, it is not obvious whether these yield an (approximately) optimal solution in polynomial time. For the ellipsoid method, the key problem is that one needs an 'a priori' bound on the norm of a minimizer that is at most exponential in the input size, and it is not clear whether such a bound exists. As our main contribution, we show that the optimization problem above can be (approximately) solved in polynomial time. To do so, we show that the norm bounds on the minimizers required by the ellipsoid method do in fact hold. Our key technical tool is a new structure theorem for convex polynomials, which shows they can be written as the sum of a linear function and a strongly convex quadratic (of potentially fewer variables). Based on joint work (in progress) with David Steurer and Manuel Wiedmer.

Biography: Lucas Slot is currently a postdoc in the Theoretical Computer Science department of ETH Zürich, within the group of David Steurer. Before, he was a PhD student at Centrum Wiskunde & Informatica (CWI) in Amsterdam, under the supervision of Monique Laurent. He defended his thesis at Tilburg University in 2022. His main research interests are in polynomial optimization and semidefinite programming approaches to problems in optimization, discrete geometry, combinatorics, statistics and data science.