5 papers
SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth
We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean hypercube for Symmetric Quadratic Functions (SQFs) in variables with roots placed in points and $…
A Technique for Obtaining True Approximations for -Center with Covering Constraints
Georg Anegg, Haris Angelidakis, Adam Kurpisz +1
There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the -Center problem in this s…
New Dependencies of Hierarchies in Polynomial Optimization
Adam Kurpisz, Timo de Wolff
We compare four key hierarchies for solving Constrained Polynomial Optimization Problems (CPOP): Sum of Squares (SOS), Sum of Diagonally Dominant Polynomials (SDSOS), Sum of Nonneg…
Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials
Mareike Dressler, Adam Kurpisz, Timo de Wolff
Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove com…
Tight Sum-of-Squares lower bounds for binary polynomial optimization problems
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
We give two results concerning the power of the Sum-of-Squares(SoS)/Lasserre hierarchy. For binary polynomial optimization problems of degree and an odd number of variables $n…