52 citations · 131 across the 29 of their papers we have counts for
3 papers · 2 filters
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
Daniel Dadush, Shashwat Garg, Shachar Lovett +1
An important theorem of Banaszczyk (Random Structures & Algorithms `98) states that for any sequence of vectors of norm at most and any convex body of Gaussian m…
On the Lattice Distortion Problem
Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz
We introduce and study the \emph{Lattice Distortion Problem} (LDP). LDP asks how "similar" two lattices are. I.e., what is the minimal distortion of a linear bijection between the…
An Algorithm for Komlós Conjecture Matching Banaszczyk's bound
Nikhil Bansal, Daniel Dadush, Shashwat Garg
We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring…