9 citations · 20 across the 7 of their papers we have counts for
5 papers · 1 filter
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…
Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
Nikhil Bansal, Shashwat Garg, Jesper Nederlof +1
We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with items using time and polynomial space, where the $O^*(\cdot…
Algorithmic Discrepancy Beyond Partial Coloring
Nikhil Bansal, Shashwat Garg
The partial coloring method is one of the most powerful and widely used method in combinatorial discrepancy problems. However, in many cases it leads to sub-optimal bounds as the p…
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…
Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems
Nikhil Bansal, Shashwat Garg
We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most sets. We give an algorithm that finds a coloring with di…