Nikhil Bansal

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 116

Top Venues

Publications

Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn
Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. CoRR (2024)
Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu
On Minimizing Generalized Makespan on Unrelated Machines. CoRR (2023)
Nikhil Bansal
EATCS Distinguished Dissertation Award for 2022. Bull. EATCS 140 (2023)
Nikhil Bansal, John Kuszmaul, William Kuszmaul
-dimensional cow-path problem. Inf. Process. Lett. 182 (2023)
Nikhil Bansal, David G. Harris
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture. Random Struct. Algorithms 62 (1) (2023)
Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali
On Min Sum Vertex Cover and Generalized Min Sum Set Cover. SIAM J. Comput. 52 (2) (2023)
Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu
On Minimizing Generalized Makespan on Unrelated Machines. APPROX/RANDOM (2023)
Nikhil Bansal, Dor Katzelnick, Roy Schwartz
Almost Logarithmic Approximation for Cutwidth and Pathwidth. CoRR (2023)
Nikhil Bansal, Haotian Jiang, Raghu Meka
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. STOC (2023)
Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof
-Server in Uniform Metrics. ACM Trans. Algorithms 19 (1) (2023)
Jae-Won Chung, Yile Gu, Insu Jang, Luoxi Meng, Nikhil Bansal, Mosharaf Chowdhury
Perseus: Removing Energy Bloat from Large Model Training. CoRR (2023)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Smoothed Analysis of the Komlós Conjecture. CoRR (2022)
Nikhil Bansal, Aditi Laddha, Santosh S. Vempala
A Unified Approach to Discrepancy Minimization. CoRR (2022)
Nikhil Bansal, Lars Rohwedder, Ola Svensson
Flow time scheduling and prefix Beck-Fiala. STOC (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. ITCS (2022)
Nikhil Bansal, Ohad N. Feldheim
The power of two choices in graphical allocation. STOC (2022)
Nikhil Bansal, Lars Rohwedder, Ola Svensson
Flow Time Scheduling and Prefix Beck-Fiala. CoRR (2022)
Nikhil Bansal, John Kuszmaul, William Kuszmaul
A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem. CoRR (2022)
Nikhil Bansal, Makrand Sinha, Ronald de Wolf
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms. CoRR (2022)
Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. ACM Trans. Algorithms 18 (4) (2022)
Nikhil Bansal, Makrand Sinha, Ronald de Wolf
Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. CCC (2022)
Nikhil Bansal, William Kuszmaul
Balanced Allocations: The Heavily Loaded Case with Deletions. CoRR (2022)
Nikhil Bansal, Aditi Laddha, Santosh S. Vempala
A Unified Approach to Discrepancy Minimization. APPROX/RANDOM (2022)
Nikhil Bansal, Christian Coester
Online Metric Allocation and Time-Varying Regularization. ESA (2022)
Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee
Learning-Augmented Weighted Paging. SODA (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Smoothed Analysis of the Komlós Conjecture. ICALP (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. CoRR (2022)
Nikhil Bansal, Ohad N. Feldheim
Well-Balanced Allocation on General Graphs. CoRR (2021)
Nikhil Bansal, Joseph (Seffi) Naor, Ohad Talmon
Efficient Online Weighted Multi-Level Paging. SPAA (2021)
Nikhil Bansal, Jatin Batra
Non-uniform Geometric Set Cover and Scheduling on Multiple Machines. SODA (2021)
Nikhil Bansal, Aravind Srinivasan, Ola Svensson
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines. SIAM J. Comput. 50 (3) (2021)
Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover. SODA (2021)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Online Discrepancy Minimization for Stochastic Arrivals. SODA (2021)
Nikhil Bansal, Christian Coester
Online metric allocation. CoRR (2021)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. CoRR (2021)
Nikhil Bansal, Ilan Reuven Cohen
Contention Resolution, Matrix Scaling and Fair Allocation. WAOA (2021)
Nikhil Bansal, Makrand Sinha
k-forrelation optimally separates Quantum and classical query complexity. STOC (2021)
Nikhil Bansal, David G. Harris
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture. CoRR (2020)
Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh
Nested Convex Bodies are Chaseable. Algorithmica 82 (6) (2020)
Susanne Albers, Nikhil Bansal, Elvira Mayordomo, Dale Miller, Jaroslav Nesetril, Damian Niwinski, David Peleg, Vladimiro Sassone, Alexandra Silva
EATCS Distinguished Dissertation Award 2020 - Call for Nominations. Bull. EATCS 132 (2020)
Nikhil Bansal, Raghu Meka
On the discrepancy of random low degree set systems. Random Struct. Algorithms 57 (3) (2020)
Nikhil Bansal, Makrand Sinha
k-Forrelation Optimally Separates Quantum and Classical Query Complexity. CoRR (2020)
Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
Online vector balancing and geometric discrepancy. STOC (2020)
Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover. CoRR (2020)
Nikhil Bansal, Makrand Sinha
$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Nikhil Bansal, Ilan Reuven Cohen
An Asymptotic Lower Bound for Online Vector Bin Packing. CoRR (2020)
Nikhil Bansal, Joel H. Spencer
On-line balancing of random inputs. Random Struct. Algorithms 57 (4) (2020)
Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. SODA (2020)
Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee
Scale-Free Allocation, Amortized Convexity, and Myopic Weighted Paging. CoRR (2020)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Online Discrepancy Minimization for Stochastic Arrivals. CoRR (2020)
Nikhil Bansal, Raghu Meka
On the discrepancy of random low degree set systems. SODA (2019)
Nikhil Bansal, Ola Svensson, Luca Trevisan
New Notions and Constructions of Sparsification for Graphs and Hypergraphs. CoRR (2019)
Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
Online Vector Balancing and Geometric Discrepancy. CoRR (2019)
Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. Theory Comput. 15 (2019)
Nikhil Bansal, Jatin Batra
Geometry of Scheduling on Multiple Machines. CoRR (2019)
Nikhil Bansal
On a generalization of iterated and randomized rounding. STOC (2019)
Nikhil Bansal, Joel H. Spencer
On-Line Balancing of Random Inputs. CoRR (2019)
Nikhil Bansal, Ola Svensson, Luca Trevisan
New Notions and Constructions of Sparsification for Graphs and Hypergraphs. FOCS (2019)
Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
)-Server Problem on Bounded Depth Trees. ACM Trans. Algorithms 15 (2) (2019)
Nikhil Bansal, Daniel Dadush, Shashwat Garg
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. SIAM J. Comput. 48 (2) (2019)
Nikhil Bansal, Anupam Gupta
Potential-Function Proofs for Gradient Methods. Theory Comput. 15 (2019)
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
New Tools and Connections for Exponential-Time Approximation. Algorithmica 81 (10) (2019)
Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, Georg von der Brüggen
Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems. CoRR (2018)
Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof
-Server in Uniform Metrics. SODA (2018)
Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems. SIAM J. Comput. 47 (5) (2018)
Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, Georg von der Brüggen
Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems. ISAAC (2018)
Nikhil Bansal
On a generalization of iterated and randomized rounding. CoRR (2018)
Nikhil Bansal, Anupam Gupta, Guru Guruganesh
On the Lovász Theta Function for Independent Sets in Sparse Graphs. SIAM J. Comput. 47 (3) (2018)
Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos, Kirk Pruhs
Tight Bounds for Double Coverage Against Weak Adversaries. Theory Comput. Syst. 62 (2) (2018)
Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
The gram-schmidt walk: a cure for the Banaszczyk blues. STOC (2018)
Nikhil Bansal, Raghu Meka
On the discrepancy of random low degree set systems. CoRR (2018)
Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. CoRR (2018)
Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh
Nested Convex Bodies are Chaseable. SODA (2018)
Nikhil Bansal, Bart Kamphorst, Bert Zwart
Achievable Performance of Blind Policies in Heavy Traffic. Math. Oper. Res. 43 (3) (2018)
Nikhil Bansal, Shashwat Garg
Algorithmic discrepancy beyond partial coloring. STOC (2017)
Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos
Weighted k-Server Bounds via Combinatorial Dichotomies. FOCS (2017)
Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
)-Server Problem on Bounded Depth Trees. SODA (2017)
Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof
Competitive Algorithms for Generalized k-Server in Uniform Metrics. CoRR (2017)
Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos
Weighted k-Server Bounds via Combinatorial Dichotomies. CoRR (2017)
Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. CoRR (2017)
Nikhil Bansal, Seeun William Umboh
Tight approximation bounds for dominating set on graphs of bounded arboricity. Inf. Process. Lett. 122 (2017)
Nikhil Bansal, Irene Finocchi
Guest Editors' Foreword. Algorithmica 78 (4) (2017)
Nikhil Bansal, Christoph Dürr, Kim Thang Nguyen, Óscar C. Vásquez
The local-global conjecture for scheduling with non-linear cost. J. Sched. 20 (3) (2017)
Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh
Nested Convex Bodies are Chaseable. CoRR (2017)
Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
Faster space-efficient algorithms for subset sum and k-sum. STOC (2017)
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
New Tools and Connections for Exponential-time Approximation. CoRR (2017)
Nikhil Bansal, Anupam Gupta
Potential-Function Proofs for First-Order Methods. CoRR (2017)
Nikhil Bansal, Daniel Reichman, Seeun William Umboh
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs. SODA (2017)
Nikhil Bansal, Viswanath Nagarajan
Approximation-Friendly Discrepancy Rounding. IPCO (2016)
Nikhil Bansal, Aravind Srinivasan, Ola Svensson
Lift-and-round to improve weighted completion time on unrelated machines. STOC (2016)
Nikhil Bansal, Kirk Pruhs
Weighted geometric set multi-cover via quasi-uniform sampling. J. Comput. Geom. 7 (1) (2016)
Nikhil Bansal, Marek Eliás, Arindam Khan
Improved Approximation for Vector Bin Packing. SODA (2016)
Nikhil Bansal, Shashwat Garg
Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems. CoRR (2016)
Nikhil Bansal, Shashwat Garg
Algorithmic Discrepancy Beyond Partial Coloring. CoRR (2016)
Nikhil Bansal, Bouke Cloostermans
Minimizing Maximum Flow-Time on Related Machines. Theory Comput. 12 (1) (2016)
Nikhil Bansal, Daniel Dadush, Shashwat Garg
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. FOCS (2016)
Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
New Bounds for the $(h, k)$-Server Problem. CoRR (2016)
Nikhil Bansal, Nicole Megow, Clifford Stein
Scheduling (Dagstuhl Seminar 16081). Dagstuhl Reports 6 (2) (2016)
Nikhil Bansal, Daniel Reichman, Seeun William Umboh
Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs. CoRR (2016)
Nikhil Bansal, Tim Oosterwijk, Tjark Vredeveld, Ruben van der Zwaan
Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. Algorithmica 76 (4) (2016)

Nikhil Bansal.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Nikhil Bansal