Shashwat Garg

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.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

- Microsoft Redmond, October 2017
- University of Washington, October 2017
- Indian Institute of Science Bangalore, January 2018

- STOC 2017, Montreal, June 2017
- Simons Institute, September 2017

- FOCS 2016, New Jersey, October 2016
- University of Washington Theory Seminar, Seattle, October 2016
- Microsoft Research Theory Group Seminar, Redmond, September 2016
- MCQMC, Stanford University, August 2016
- Highlights of Algorithms (HALG 2016), Short Contributed Talk, Paris, June 2016
- 5th SDP Day, CWI Amsterdam, June 2016
- Theory Seminar, IIT Delhi, April 2016

- Highlights of Algorithms (HALG 2017), Short Contributed Talk, Berlin, June 2017
- Combinatorial Optimization meets Parameterized Complexity Workshop, University of Bonn, December 2016