1 citations · 1 across the 7 of their papers we have counts for
3 papers · 1 filter
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 $…
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…
On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
The Lasserre/Sum-of-Squares (SoS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy con…