81 citations · 136 across the 38 of their papers we have counts for
4 papers · 1 filter
Forall-exist statements in pseudopolynomial time
Eleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss +1
Given a convex set and an integer matrix , we consider statements of the form s.t. $Wx \leq…
The Subspace Flatness Conjecture and Faster Integer Programming
Victor Reis, Thomas Rothvoss
In a seminal paper, Kannan and Lovász (1988) considered a quantity which denotes the best volume-based lower bound on the covering radius of a convex body $K…
From approximate to exact integer programming
Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoss
Approximate integer programming is the following: For a convex body , either determine whether is empty, or find an integer point in…
An Improved Deterministic Rescaling for Linear Programming Algorithms
Rebecca Hoberg, Thomas Rothvoss
The perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due…