19 citations · 30 across the 17 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…
Stronger Coreset Bounds for Kernel Density Estimators via Chaining
Rainie Bozzai, Thomas Rothvoss
We apply the discrepancy method and a chaining approach to give improved bounds on the coreset complexity of a wide class of kernel functions. Our results give randomized polynomia…
Optimal Online Discrepancy Minimization
Janardhan Kulkarni, Victor Reis, Thomas Rothvoss
We prove that there exists an online algorithm that for any sequence of vectors with , arriving one at a time, decides random si…
Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity
Sally Dong, Thomas Rothvoss
We show that any bounded integral function with rank has deterministic communication complexity $Δ^{O(Δ)} \cdot \sqrt{r} \cdot \log r…