Thomas Rothvoss

collaborators

2 papers

cs.CC2026

A note on the $Σ_{2}^{P}$ -completeness of the Frobenius number

Thomas Rothvoss

Given a finite set $A$ of natural numbers whose greatest common divisor is one, the Frobenius number $g (A)$ is the largest integer that is not a non-negative integer combination of…

cs.DS2026

Nearly-Tight Bounds for Zonotope Containment and Beyond

Friedrich Eisenbrand, Thomas Rothvoss, Matteo Russo +1

We investigate the convex-body containment problem $max {s > 0 : s Z \subseteq Q}$ , where the outer body $Q \subseteq R^{d}$ is described by a membership oracle and the inne…

A note on the Σ2P​-completeness of the Frobenius number

Nearly-Tight Bounds for Zonotope Containment and Beyond

A note on the $Σ_{2}^{P}$ -completeness of the Frobenius number