Selected recent publications

Well-balanced allocation on general graphs. Nikhil Bansal, Ohad Feldheim. Arxiv.
Scale-free Allocation, amortized Convexity and Myopic Paging. Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee. Arxiv
k-Forrelation Optimally Separates Quantum and Classical Query Complexity. Nikhil Bansal, Makrand Sinha, STOC 2021.
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.