Researcher at CWI, Amsterdam in the Networks
and Optimization Group

Professor, Department of Math and CS, Eindhoven University of Technology.

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 Gradient Methods. Nikhil Bansal, Anupam
Gupta.

Algorithmic Aspects of Discrepancy. Chapter in the book Panorama of Discrepancy Theory.

**Current and Past Advisees:**

Phd: Marek Elias, Shashwat Garg,
Greg Koumoutsous, Bart Kamphort
(joint), Jorn van der Pol (joint)

Postdoc: Christian Coester, Ilan
Cohen, Jatin Batra, Makrand Sinha (joint),** **Laszlo Kozma, Thijs Laarhoeven,
Lukasz Jez, William Seeun Umboh

**Recent Teaching:**

Notes for IPCO summer school (lec1, lec2, slides, exercises)

Randomized Algorithms (Sp 2021).

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:** CWI
N&O seminar, Hierarchies
Reading Group, Eindhoven
Discrete Math Seminar

**Service:
**Editorial Boards: Journal of the ACM, Theory of Computing, Stochastic
Models.

Previously SICOMP (2012-2018), SIDMA (2012-2018), Math of Operations Research (2013-2020)

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

Workshop Organization:

STOC 2020 Workshop
on Recent advanced in discrepancy and applications

6^{th}
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

5^{th}
SDP Days, Jun 2016, CWI Amsterdam

Dagstuhl Seminar on Scheduling, Feb 2016, Germany

Relaxation
Workshop, Nov 2015, HIM, Bonn

Scheduling
under Uncertainty, June 2015, Eindhoven

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

4^{th} SDP Days,
March 2013, CWI Amsterdam

**Selected Recent Publications:**

k-Forrelation Optimally Separates
Quantum and Classical Query Complexity. Nikhil Bansal, Makrand Sinha,
ECCC.

Scale-free Allocation, amortized
Convexity and Myopic Paging. Nikhil Bansal, Christian Coester,
Ravi Kumar, Manish Purohit, Erik Vee.
Arxiv

Online Discrepancy Minimization for
Stochastic Arrivals. Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha. SODA 2021.

Improved Approximations for
Min Sum Vertex Cover and Generalized Min Sum Set Cover. Nikhil
Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali.
SODA 2021

Geometry of scheduling on multiple
machines. Nikhil Bansal, Jatin Batra. SODA 2021.

Online vector balancing and
geometric discrepancy. Nikhil Bansal, Haotian
Jiang, Janardhan Kulkarni, Sahil
Singla. STOC 2020.**
**On-line balancing of random
inputs. Nikhil Bansal, Joel Spencer. Random Structures and Algorithms, to
appear.

Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh. SODA 2020.

Potential-Function Proofs for Gradient Methods. Nikhil Bansal, Anupam Gupta. Theory of Computing 2019.

New notions and constructions of sparsification for graphs and hypergraphs. Nikhil Bansal, Ola Svensson, Luca Trevisan. FOCS 2019.

On a generalization of iterated and randomized rounding. Nikhil Bansal. STOC 2019.

On the
discrepancy of random low degree set systems. Nikhil Bansal, Raghu Meka. SODA 2019.

Achievable
performance of blind policies in heavy traffic. Nikhil Bansal, Bart Kamphorst, Bert Zwart. Math of OR
43(3), 949-964, 2018.

The Gram-Schmidt Walk: A cure for the
Banaszczyk blues. Nikhil Bansal, Daniel Dadush, Shashwat
Garg, Shachar Lovett. STOC 2018.

Competitive
Algorithms for Generalized k-server in uniform metrics. Nikhil Bansal,
Marek Elias, Grigorios Koumoutsos,
Jesper Nederlof. SODA 2018.

Nested
Convex Bodies are Chaseable. Nikhil Bansal,
Martin Bohm, Marek Elias, Grigorios Koumoutsos, Seeun William Umboh. SODA 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 Reichman, Seeun 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)