Thomas Rothvoss

activity

20242026

most citedThe Subspace Flatness Conjecture and Faster Integer Programming

1 citations · 1 across the 2 of their papers we have counts for

collaborators

7 papers

math.MG2026

Linear-size $ℓ_{1}$ sparsifiers

Victor Reis, Thomas Rothvoss

We prove that for any matrix $A \in R^{m \times n}$ and any $ε > 0$ there is a diagonal matrix $D \in R_{\geq 0}^{m \times m}$ with at most $O(\frac{n}{…

math.OC2026★ 1 cited

The Subspace Flatness Conjecture and Faster Integer Programming

Victor Reis, Thomas Rothvoss

In a seminal paper, Kannan and LovÃ¡sz (1988) considered a quantity $I^¼_{K L} (I^, K)$ which denotes the best volume-based lower bound on the covering radius $I^¼ (I^, K)$ of a convex bo…

cs.DS2026

A Tale of Santa Claus, Hypergraphs and Matroids

Sami Davies, Thomas Rothvoss, Yihao Zhang

A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set…

cs.DM2025

Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure

Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi +2

For a real matrix $A \in R^{d \times n}$ with non-collinear columns, we show that $n \leq O (d^{4} I^º_{A})$ where $I^º_{A}$ is the \emph{circuit imbalance measure} of $A$ . The cir…

cs.CC2025

A parameterized linear formulation of the integer hull

Friedrich Eisenbrand, Thomas Rothvoss

Let $A \in Z^{m \times n}$ be an integer matrix with components bounded by $I^$ in absolute value. Cook et al.~(1986) have shown that there exists a universal matrix $B \i…

cs.LG2025

DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory

Jerry Chee, Arturs Backurs, Rainie Heck +4

Quantizing the weights of a neural network has two steps: (1) Finding a good low bit-complexity representation for weights (which we call the quantization grid) and (2) Rounding th…