USI - Email

Archive / INF Seminars / INF_2019_11_29_Adam_Kurpisz

USI - Email

	New Dependencies of Semialgebraic Proof Systems in Polynomial Optimization

Host: Prof. Antonio Carzaniga

Friday

29.11

USI Lugano Campus, room SI-007, Informatics building

10:30-11:30


	Adam Kurpisz ETH Zurich, Switzerland

Abstract:
One of the most promising approaches in constructing efficient algorithms for Constrained Polynomial Optimization Problems (CPOP) is based on certifying non-negativity of polynomials over basic semialgebraic sets.
We compare four key hierarchies for solving CPOP arising from semialgebraic proof systems: Sum of Squares (SOS), Sum of Diagonally Dominant (SDSOS), Sum of Nonnegative Circuits (SONC), and the Sherali Adams (SA). We prove a collection of dependencies among these hierarchies both for general CPOPs and for optimization problems on the Boolean hypercube. The results presented in this talk complete the current understanding of the dependencies among these semialgebraic proof systems.

Biography:
Adam Kurpisz is Head of Ambizione Junior Research Group at the Institute for Operations Research of the Department of Mathematics at ETH Zurich. Before joining ETH Zurich he was a postdoctoral researcher and an exchange PhD student at IDSIA under the supervision of Prof. Monaldo Mastrolilli and a visiting researcher at Max-Planck-Institut für Informatik hosted by Prof. Andreas Wiese. He obtained his PhD degree under supervision of Prof. Paweł Zieliński at the Department of Computer Science of the Faculty of Fundamental Problems of Technology at Wrocław University of Science and Technology.
His research interests are focused on Combinatorial Optimization problems both from the perspective of constructing efficient algorithms and proving complexity bounds. The core of his research is applying methods from Real Algebraic Geometry to construct and analyze Semi-algebraic Proof Systems that, in turns, provide unified algorithmic frameworks (e.g. Sum-of-Squares algorithm).