1 citations · 1 across the 7 of their papers we have counts for
14 papers
On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
Adam Kurpisz, Lucas Slot, Mikhail Zaytsev
We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of for 0/1 variables under the constraint $\s…
IMProofBench: Benchmarking AI on Research-Level Mathematical Proof Generation
Johannes Schmitt, Gergely Bérczi, Jasper Dekoninck +57
As the mathematical capabilities of large language models (LLMs) improve, it becomes increasingly important to evaluate their performance on research-level tasks at the frontier of…
On the SDP Relaxation of Direct Torque Finite Control Set Model Predictive Control
Luca M. Hartmann, Orcun Karaca, Tinus Dorfling +2
This paper formulates a semidefinite programming relaxation for a long horizon direct-torque finite-control-set model predictive control problem. In parallel with this relaxation,…
A Wiener Process Perspective on Local Intrinsic Dimension Estimation Methods
Piotr Tempczyk, Łukasz Garncarek, Dominik Filipiak +1
Local intrinsic dimension (LID) estimation methods have received a lot of attention in recent years thanks to the progress in deep neural networks and generative modeling. In oppos…
Improved Approximations for Translational Packing of Convex Polygons
Adam Kurpisz, Silvan Suter
Optimal packing of objects in containers is a critical problem in various real-life and industrial applications. This paper investigates the two-dimensional packing of convex polyg…
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…
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
The Min-sum single machine scheduling problem (denoted 1||sum f_j) generalizes a large number of sequencing problems. The first constant approximation guarantees have been obtained…
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…
Sum-of-squares hierarchy lower bounds for symmetric formulations
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical…
Approximability of the robust representatives selection problem
Adam Kasperski, Adam Kurpisz, Pawel Zielinski
In this paper new complexity and approximation results on the robust versions of the representatives selection problem, under the scenario uncertainty representation, are provided,…