Shashwat Garg
photo

I am a third 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.

Currently, I am at the Simons Institute for the Bridging Continuous and Discrete Optimization workshop.

I have a broad interest in theoretical computer science. In particular, I am interested in discrepancy, approximation algorithms and hierarchies.

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

The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues [pdf | summary]
with Nikhil Bansal, Daniel Dadush, Shachar Lovett.

Quasi-PTAS for Scheduling with Precedences using LP Hierarchies [pdf | summary]

Faster Space-Efficient Algorithms for Subset Sum and k-Sum [pdf | summary]
with Nikhil Bansal, Jesper Nederlof, Nikhil Vyas. STOC 2017.

Algorithmic Discrepancy Beyond Partial Coloring [pdf | summary | Nikhil's TCS+ talk]
with Nikhil Bansal. STOC 2017.


2016

An Algorithm for Komlós Conjecture Matching Banaszczyk's bound [pdf | summary | FOCS talk]
with Nikhil Bansal, Daniel Dadush. FOCS 2016. Invited to FOCS special issue.

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.

Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems [pdf | summary]
with Nikhil Bansal


2015

Tighter estimates for ε-nets for disks [pdf | summary]
with Norbert Bus, Nabil Mustafa, Saurabh Ray

Improved Local Search for Geometric Hitting Set [pdf | summary]
with Norbert Bus, Nabil Mustafa, Saurabh Ray. STACS 2015


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


An Algorithm for Komlós Conjecture Matching Banaszczyk's bound Algorithmic Discrepancy Beyond Partial Coloring Faster Space-Efficient Algorithms for Subset Sum and k-Sum