19 citations · 30 across the 17 of their papers we have counts for
4 papers · 1 filter
Approximate in time -- now in any norm!
Thomas Rothvoss, Moritz Venzin
We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time . This contrasts the correspondin…
Improved Analysis of Online Balanced Clustering
Marcin Bienkowski, Martin Böhm, Martin Koutecký +3
In the online balanced graph repartitioning problem, one has to maintain a clustering of nodes into clusters, each having nodes. During runtime, an online…
Tight bounds on the Fourier growth of bounded functions on the hypercube
Siddharth Iyer, Anup Rao, Victor Reis +2
We give tight bounds on the degree homogenous parts of a bounded function on the cube. We show that if has degree , then…
On the Hardness of Scheduling With Non-Uniform Communication Delays
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +3
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair o…