I am a second year PhD student at the Mathematics and Computer Science Department of TU Eindhoven. I am fortunate to have

Nikhil Bansal as my advisor. Previously, I finished my bachelor's degree in Computer Science and Engineering from the Indian Institute of Technology, Delhi where I worked with

Naveen Garg.

I have a broad interest in theoretical computer science. Most of my research has been on discrepancy theory and approximation algorithms.

You can reach me at s.garg (at) tue (dot) nl or garg.shashwat (at) gmail (dot) com

Here is my

CV and list of

publications.

DBLP profile

2017

**Faster Space-Efficient Algorithms for Subset Sum and k-Sum**
[pdf | summary]

with Nikhil Bansal, Jesper Nederlof, Nikhil Vyas. To appear in STOC 2017.

We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instaces with n items using O^{*}(2^{0.86n}) time and polynomial space, assuming random read-only access to random bits. Modulo this mild assumption, this resolves a long standing open problem.
The main tool behind this is an algorithm to determine whether two given lists have a common element. Assuming random read-only access to random bits, we show how to solve this problem using less space and significantly faster than the trivial algorithms. We also show how to apply this to random instances of k-sum to get improved space-time tradeoffs.

**Algorithmic Discrepancy Beyond Partial Coloring**
[pdf | summary | TCS+ talk]

with Nikhil Bansal. To appear in STOC 2017.

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 partial coloring step must be iterated a logarithmic number of times, and the errors can add up
in an adversarial way.
We give a new and general algorithmic framework that overcomes the limitations of the partial coloring method and can be applied in a black-box manner to various problems. Using this framework, we give new improved bounds and algorithms for several classic problems in discrepancy. In particular, for Tusnady’s problem dealing with discrepancy of axis-parallel rectangles, and more generally d-dimensional boxes, we give algorithmic bounds which are better than even the existential bounds known prior to this work. Similarly, for the Steinitz problem we give the first algorithm that matches the best known non-constructive bounds due to Banaszczyk in the L_{∞} case, and improves the previous algorithmic bounds substantially in the L_{2} case.

2016

**An Algorithm for Komlós Conjecture Matching Banaszczyk's bound **
[pdf | summary]

with Nikhil Bansal, Daniel Dadush. FOCS 2016. *Invited to FOCS special issue.*

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 with discrepancy matching the best known non-constructive bound for the problem due to Banaszczyk. Our result also extends to the more general Komlós setting where we also match the bound given by Banaszczyk.

**Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem **
[pdf | summary]

with Daniel Dadush, Shachar Lovett, Aleksandar Nikolov. RANDOM 2016. *Invited to RANDOM special issue.*

We look at the more general question of getting an algorithm for Banaszczyk's discrepancy theorem for general convex bodies. We show that it is equivalent to finding a certain subgaussian distribution and also give an algorithm if the vectors are small.

**Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems**
[pdf | summary]

with Nikhil Bansal

We considered the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets and gave improved bounds when the maximum set size is small. This paper is now obsolete and has been vastly improved by the paper "An Algorithm for Komlós Conjecture Matching Banaszczyk's bound".

2015

**Tighter estimates for ε-nets for disks **
[pdf | summary]

with Norbert Bus, Nabil Mustafa, Saurabh Ray

We give improved bounds for size of ε-net for disks in the plane.

**Improved Local Search for Geometric Hitting Set **
[pdf | summary]

with Norbert Bus, Nabil Mustafa, Saurabh Ray. STACS 2015

We look at the hitting set problem for disks in the plane. We show that a local search algorithm, which only considers small swaps, gives good approximations and has a much better running time than previous algorithms.

2014

**Competitive Analysis of Bidirectional Scheduling**
[link to Elisabeth's thesis, chapter 4]

with Elisabeth Lübbecke, Nicole Megow

**Predicting Relevant Documents for Enterprise Communication Contexts**
[pdf]

with Krishna K. Dhara, Venkatesh Krishnaswamy. ICUIMC 2014