32 citations · 34 across the 5 of their papers we have counts for
5 papers
A Fourier-Analytic Approach for the Discrepancy of Random Set Systems
Rebecca Hoberg, Thomas Rothvoss
One of the prominent open problems in combinatorics is the discrepancy of set systems where each element lies in at most sets. The Beck-Fiala conjecture suggests that the right…
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…
Number Balancing is as hard as Minkowski's Theorem and Shortest Vector
Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss +1
The number balancing (NBP) problem is the following: given real numbers , find two disjoint subsets so that the difference $|\sum_…
A Logarithmic Additive Integrality Gap for Bin Packing
Rebecca Hoberg, Thomas Rothvoss
For bin packing, the input consists of items with sizes which have to be assigned to a minimum number of bins of size 1. Recently, the second author gav…
The Theory of Pseudoknots
Allison Henrich, Rebecca Hoberg, Slavik Jablan +3
Classical knots in can be represented by diagrams in the plane. These diagrams are formed by curves with a finite number of transverse crossings, where each crossing…