Nikhil Bansal

Professor, Department of Mathematics and Computer Science
Eindhoven University of Technology.  
I also work at CWI, Amsterdam in the  Networks and Optimization Group 

Contact information  Brief Bio  and CV

Research interests:  Theoretical computer science with emphasis on design and analysis of algorithms for discrete optimization problems.
I also dabble in related areas such as discrete math, complexity theory, machine learning and probability.

Some Surveys:
Potential-Function Proofs for First-Order Methods. Nikhil Bansal, Anupam Gupta.
Algorithmic Aspects of Discrepancy.  Chapter in the book Panorama of Discrepancy Theory.

New developments in iterated rounding. Write up for a talk at FSTTCS 2014.

Current Advisees:

PhdMarek Elias, Shashwat Garg, Greg Koumoutsous,   
Postdoc: Laszlo Kozma, Thijs Laarhoeven

 

Recent Teaching:

Algorithms beyond worst case (Sp 2018). Some lecture notes. 

Advanced Semidefinite Programming (Sp 2017)
Algorithms and Uncertainty: Fall 2016  (at UC Berkeley)

Graphs and Algorithms (2MMD30)
Approximation Algorithms (2WO07)
Freshman Linear Algebra

Seminars:  Hierarchies Reading Group,  Eindhoven Discrete Math Seminar

Service:
Editorial Boards: Journal of the ACM, SIAM  Journal on Computing, Mathematics of  Operations Research

Recent Program Committees: FOCS 2018, HALG 2018, ICALP 2018,  Approx 2017, IPCO 2017, SPAA 2017,
IPDPS 2017, WAOA2016, ITCS 2016, ESA 2015 (chair), STOC 2014FOCS 2014, ICALP 2014 

 

Workshop Organization:

6th SDP Day, Apr 2018, CWI Amsterdam

Semester on Bridging Continuous and Discrete Optimization, Fall 2017 at UC Berkeley

Optimization and Decision-Making Under Uncertainty, Oct 2016, UC Berkeley

5th SDP Days, Jun 2016, CWI Amsterdam

Dagstuhl Seminar on Scheduling, Feb 2016

Relaxation Workshop, Nov 2015, HIM, Bonn

Scheduling under Uncertainty, June 2015, Eindhoven

Stochastic Activity Month: Probability and Combinatorics, Jan 2014, Eindoven

4th SDP Days, March 2013, CWI Amsterdam

Selected Recent Publications:
The Gram-Schmidt Walk: A cure for the Banaszczyk blues. Nikhil Bansal, Daniel Dadush,  Shashwat Garg, Shachar Lovett. STOC 2018.
Weighted k-server bounds via combinatorial dichotomies. Nikhil Bansal, Marek Elias, Greg Koumoutsos. FOCS 2017.
Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
. Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas. STOC 2017.
Algorithmic discrepancy beyond partial coloring.
Nikhil Bansal, Shashwat Garg, STOC 2017.
Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
. Nikhil Bansal, Daniel ReichmanSeeun William Umboh. SODA 2017.
New Bounds for the (h, k)-Server Problem. Nikhil Bansal, Marek Elias, Lukasz Jez, Greg Koumousos. SODA 2017
Algorithm for Komlos Conjecture: Matching Banaszczyk’s bound. Nikhil Bansal, Daniel Dadush and Shashwat Garg. FOCS 2016.  Invited to FOCS special issue.
Lift and Round to improve weighted completion time on unrelated machines. Nikhil Bansal, Aravind Srinivasan and Ola Svensson. STOC 2016. Invited to STOC special issue.
Approximation-Friendly Discrepancy Rounding. Nikhil Bansal and Viswanath Nagarajan. IPCO 2016.
Improved Approximation for Vector Bin Packing. Nikhil Bansal, Marek Elias and Arindam Khan. SODA 2016.
On the Lovasz theta function for independent sets. Nikhil Bansal, Anupam Gupta and Guru Guruganesh. STOC 2015. Invited to STOC special issue.
Approximating independent set in sparse graphs. Nikhil Bansal. SODA 2015.
Minimizing flow-time on unrelated machines. Nikhil Bansal and Janardhan Kulkarni. STOC 2015.

Full list: (DBLP, Google Scholar)