Shashwat Garg
photo

I am a third (and final) 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. 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


2018

Quasi-PTAS for Scheduling with Precedences using LP Hierarchies [pdf | summary]
ICALP 2018. Best Student Paper award.

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

Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Sum of Completion Times and Makespan
with Janardhan Kulkarni, Shi Li.


2017

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


The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues Algorithmic Discrepancy Beyond Partial Coloring An Algorithm for Komlós Conjecture Matching Banaszczyk's bound Faster Space-Efficient Algorithms for Subset Sum and k-Sum