| 2026 | COLT | Cloning is as Hard as Learning for Stabilizer States. | Nikhil Bansal, Matthias C. Caro, Gaurav Mahajan |
| 2026 | ICALP | Expander Decomposition with Almost Optimal Overhead. | Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak |
| 2026 | STOC | Decoupling via Affine Spectral-Independence: Beck-Fiala and Komls Bounds beyond Banaszczyk. | Nikhil Bansal, Haotian Jiang |
| 2025 | FOCS | Optimal 4-Approximation for the Correlated Pandora's Problem. | Nikhil Bansal, Zhiyi Huang, Zixuan Zhu |
| 2025 | FOCS | An Improved Bound for the Beck-Fiala Conjecture. | Nikhil Bansal, Haotian Jiang |
| 2025 | SODA | Quasi-Monte Carlo Beyond Hardy-Krause. | Nikhil Bansal, Haotian Jiang |
| 2024 | FOCS | Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. | Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn |
| 2024 | FOCS | On Approximating Cutwidth and Pathwidth. | Nikhil Bansal, Dor Katzelnick, Roy Schwartz |
| 2024 | SOSP | Reducing Energy Bloat in Large Model Training. | Jae-Won Chung, Yile Gu, Insu Jang, Luoxi Meng, Nikhil Bansal, Mosharaf Chowdhury |
| 2023 | STOC | Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. | Nikhil Bansal, Haotian Jiang, Raghu Meka |
| 2022 | ESA | Online Metric Allocation and Time-Varying Regularization. | Nikhil Bansal, Christian Coester |
| 2022 | FOCS | Balanced Allocations: The Heavily Loaded Case with Deletions. | Nikhil Bansal, William Kuszmaul |
| 2022 | ICALP | Smoothed Analysis of the Komls Conjecture. | Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha |
| 2022 | SODA | Learning-Augmented Weighted Paging. | Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee |
| 2022 | STOC | The power of two choices in graphical allocation. | Nikhil Bansal, Ohad N. Feldheim |
| 2022 | STOC | Flow time scheduling and prefix Beck-Fiala. | Nikhil Bansal, Lars Rohwedder, Ola Svensson |
| 2021 | SODA | Non-uniform Geometric Set Cover and Scheduling on Multiple Machines. | Nikhil Bansal, Jatin Batra |
| 2021 | SODA | Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover. | Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali |
| 2021 | SODA | Online Discrepancy Minimization for Stochastic Arrivals. | Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha |
| 2021 | STOC | k-forrelation optimally separates Quantum and classical query complexity. | Nikhil Bansal, Makrand Sinha |
| 2021 | SPAA | Efficient Online Weighted Multi-Level Paging. | Nikhil Bansal, Joseph (Seffi) Naor, Ohad Talmon |
| 2021 | WAOA | Contention Resolution, Matrix Scaling and Fair Allocation. | Nikhil Bansal, Ilan Reuven Cohen |
| 2020 | SODA | Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. | Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh |
| 2020 | STOC | Online vector balancing and geometric discrepancy. | Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha |
| 2019 | FOCS | New Notions and Constructions of Sparsification for Graphs and Hypergraphs. | Nikhil Bansal, Ola Svensson, Luca Trevisan |
| 2019 | SODA | On the discrepancy of random low degree set systems. | Nikhil Bansal, Raghu Meka |
| 2019 | STOC | On a generalization of iterated and randomized rounding. | Nikhil Bansal |
| 2018 | ISAAC | Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems. | Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, Georg von der Brggen |
| 2018 | SODA | Competitive Algorithms for Generalized | Nikhil Bansal, Marek Elis, Grigorios Koumoutsos, Jesper Nederlof |
| 2018 | SODA | Nested Convex Bodies are Chaseable. | Nikhil Bansal, Martin Bhm, Marek Elis, Grigorios Koumoutsos, Seeun William Umboh |
| 2018 | STOC | The gram-schmidt walk: a cure for the Banaszczyk blues. | Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett |
| 2017 | FOCS | Weighted k-Server Bounds via Combinatorial Dichotomies. | Nikhil Bansal, Marek Elis, Grigorios Koumoutsos |
| 2017 | SODA | LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs. | Nikhil Bansal, Daniel Reichman, Seeun William Umboh |
| 2017 | SODA | The ( | Nikhil Bansal, Marek Elis, Lukasz Jez, Grigorios Koumoutsos |
| 2017 | STOC | Algorithmic discrepancy beyond partial coloring. | Nikhil Bansal, Shashwat Garg |
| 2017 | STOC | Faster space-efficient algorithms for subset sum and k-sum. | Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas |
| 2016 | FOCS | An Algorithm for Komls Conjecture Matching Banaszczyk's Bound. | Nikhil Bansal, Daniel Dadush, Shashwat Garg |
| 2016 | IPCO | Approximation-Friendly Discrepancy Rounding. | Nikhil Bansal, Viswanath Nagarajan |
| 2016 | SODA | Improved Approximation for Vector Bin Packing. | Nikhil Bansal, Marek Elis, Arindam Khan |
| 2016 | STOC | Lift-and-round to improve weighted completion time on unrelated machines. | Nikhil Bansal, Aravind Srinivasan, Ola Svensson |
| 2015 | SODA | Approximating independent sets in sparse graphs. | Nikhil Bansal |
| 2015 | STOC | On the Lovsz Theta function for Independent Sets in Sparse Graphs. | Nikhil Bansal, Anupam Gupta, Guru Guruganesh |
| 2015 | STOC | Minimizing Flow-Time on Unrelated Machines. | Nikhil Bansal, Janardhan Kulkarni |
| 2015 | WAOA | Tight Bounds for Double Coverage Against Weak Adversaries. | Nikhil Bansal, Marek Elis, Lukasz Jez, Grigorios Koumoutsos, Kirk Pruhs |
| 2014 | IPCO | On the Adaptivity Gap of Stochastic Orienteering. | Nikhil Bansal, Viswanath Nagarajan |
| 2014 | LATIN | Approximating Real-Time Scheduling on Identical Machines. | Nikhil Bansal, Cyriel Rutten, Suzanne van der Ster, Tjark Vredeveld, Ruben van der Zwaan |
| 2014 | LATIN | Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. | Nikhil Bansal, Tjark Vredeveld, Ruben van der Zwaan |
| 2014 | SODA | Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach. | Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li |
| 2014 | SODA | Improved Approximation Algorithm for Two-Dimensional Bin Packing. | Nikhil Bansal, Arindam Khan |
| 2013 | SODA | On the number of matroids. | Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol |
| 2012 | ESA | Weighted Geometric Set Multi-cover via Quasi-uniform Sampling. | Nikhil Bansal, Kirk Pruhs |
| 2012 | STOC | Tight time-space tradeoff for mutual exclusion. | Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally |
| 2012 | WAOA | The Primal-Dual Approach for Online Algorithms. | Nikhil Bansal |
| 2011 | ESA | Deterministic Discrepancy Minimization. | Nikhil Bansal, Joel Spencer |
| 2011 | FOCS | A Polylogarithmic-Competitive Algorithm for the k-Server Problem. | Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor |
| 2011 | FOCS | Min-max Graph Partitioning and Small Set Expansion. | Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz |
| 2011 | PODC | Minimum congestion mapping in a cloud. | Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan, Murtaza Zafer |
| 2010 | ESA | When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings - (Extended Abstract). | Nikhil Bansal, Anupam Gupta, Jian Li, Julin Mestre, Viswanath Nagarajan, Atri Rudra |
| 2010 | FOCS | Constructive Algorithms for Discrepancy Minimization. | Nikhil Bansal |
| 2010 | FOCS | The Geometry of Scheduling. | Nikhil Bansal, Kirk Pruhs |
| 2010 | ICALP | Metrical Task Systems and the | Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2010 | ICALP | Approximation Algorithms for Diversified Search Ranking. | Nikhil Bansal, Kamal Jain, Anna Kazeykina, Joseph Naor |
| 2010 | ICALP | Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. | Nikhil Bansal, Subhash Khot |
| 2010 | ICALP | Better Scalable Algorithms for Broadcast Scheduling. | Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan |
| 2010 | IPCO | On Generalizations of Network Design Problems with Degree Bounds. | Nikhil Bansal, Rohit Khandekar, Jochen Knemann, Viswanath Nagarajan, Britta Peis |
| 2010 | IPCO | On | Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, Aravind Srinivasan |
| 2010 | SODA | Towards the Randomized k-Server Conjecture: A Primal-Dual Approach. | Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2010 | SODA | A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover. | Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy |
| 2009 | FOCS | Optimal Long Code Test with One Free Bit. | Nikhil Bansal, Subhash Khot |
| 2009 | FOCS | Regularity Lemmas and Combinatorial Algorithms. | Nikhil Bansal, Ryan Williams |
| 2009 | ICALP | Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. | Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs, Dmitriy Katz |
| 2009 | ISAAC | A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability. | Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prdel, Maxim Sviridenko |
| 2009 | JSSPP | Job Admission and Resource Allocation in Distributed Streaming Systems. | Joel L. Wolf, Nikhil Bansal, Kirsten Hildrum, Sujay S. Parekh, Deepak Rajan, Rohit Wagle, Kun-Lung Wu |
| 2009 | SODA | Weighted flow time does not admit O(1)-competitive algorithms. | Nikhil Bansal, Ho-Leung Chan |
| 2009 | SODA | Speed scaling with an arbitrary power function. | Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs |
| 2009 | SODA | A logarithmic approximation for unsplittable flow on line graphs. | Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour |
| 2008 | AAIM | Speed Scaling with a Solar Cell. | Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs |
| 2008 | ICALP | Scheduling for Speed Bounded Processors. | Nikhil Bansal, Ho-Leung Chan, Tak Wah Lam, Lap-Kei Lee |
| 2008 | INFOCOM | Towards Optimal Resource Allocation in Partial-Fault Tolerant Applications. | Nikhil Bansal, Ranjita Bhagwan, Navendu Jain, Yoonho Park, Deepak S. Turaga, Chitra Venkatramani |
| 2008 | ISI | Transport security using mobile technology. | P. Panjiyar, P. Mourya, Nikhil Bansal, P. Srivastava, A. Mukherjee |
| 2008 | LATIN | Average Rate Speed Scaling. | Nikhil Bansal, David P. Bunde, Ho-Leung Chan, Kirk Pruhs |
| 2008 | Middleware | SODA: An Optimizing Scheduler for Large-Scale Stream-Based Distributed Computer Systems. | Joel L. Wolf, Nikhil Bansal, Kirsten Hildrum, Sujay S. Parekh, Deepak Rajan, Rohit Wagle, Kun-Lung Wu, Lisa Fleischer |
| 2008 | STOC | Randomized competitive algorithms for generalized caching. | Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2008 | STOC | Additive guarantees for degree bounded directed network design. | Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan |
| 2007 | COLT | Robust Reductions from Ranking to Classification. | Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin |
| 2007 | ESA | An | Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph Naor |
| 2007 | FOCS | A Primal-Dual Randomized Algorithm for Weighted Paging. | Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2007 | FOCS | Non-Preemptive Min-Sum Scheduling with Resource Augmentation. | Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, Baruch Schieber |
| 2007 | ICALP | Competitive Algorithms for Due Date Scheduling. | Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs |
| 2007 | SODA | Dynamic pricing for impatient bidders. | Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko |
| 2007 | SODA | Harmonic algorithm for 3-dimensional strip packing problem. | Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, Guochuan Zhang |
| 2007 | SODA | Speed scaling for weighted flow time. | Nikhil Bansal, Kirk Pruhs, Clifford Stein |
| 2007 | VLSID | Automatic Power Modeling of Infrastructure IP for System-on-Chip Power Analysis. | Nikhil Bansal, Kanishka Lahiri, Anand Raghunathan |
| 2006 | FOCS | Improved approximation algorithms for multidimensional bin packing problems. | Nikhil Bansal, Alberto Caprara, Maxim Sviridenko |
| 2006 | SODA | Improved approximation algorithms for broadcast scheduling. | Nikhil Bansal, Don Coppersmith, Maxim Sviridenko |
| 2006 | STOC | A quasi-PTAS for unsplittable flow on line graphs. | Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber |
| 2006 | STOC | The Santa Claus problem. | Nikhil Bansal, Maxim Sviridenko |
| 2005 | FOCS | A Tale of Two Dimensional Bin Packing. | Nikhil Bansal, Andrea Lodi, Maxim Sviridenko |
| 2005 | SODA | Approximating the average response time in broadcast scheduling. | Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor |
| 2005 | SODA | Job shop scheduling with unit processing times. | Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko |
| 2005 | VLSID | Power Monitors: A Framework for System-Level Power Estimation Using Heterogeneous Power Models. | Nikhil Bansal, Kanishka Lahiri, Anand Raghunathan, Srimat T. Chakradhar |
| 2005 | STACS | Speed Scaling to Manage Temperature. | Nikhil Bansal, Kirk Pruhs |
| 2004 | CPM | Efficient Algorithms for Finding Submasses in Weighted Strings. | Nikhil Bansal, Mark Cieliebak, Zsuzsanna Liptk |
| 2004 | DATE | Network Topology Exploration of Mesh-Based Coarse-Grain Reconfigurable Architectures. | Nikhil Bansal, Sumit Gupta, Nikil D. Dutt, Alexandru Nicolau, Rajesh Gupta |
| 2004 | FOCS | Dynamic Speed Scaling to Manage Energy and Temperature. | Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs |
| 2004 | FPL | Interconnect-Aware Mapping of Applications to Coarse-Grain Reconfigurable Architectures. | Nikhil Bansal, Sumit Gupta, Nikil D. Dutt, Alexandru Nicolau, Rajesh K. Gupta |
| 2004 | ICALP | Further Improvements in Competitive Guarantees for QoS Buffering. | Nikhil Bansal, Lisa Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko |
| 2004 | LATIN | Server Scheduling in the Weighted l | Nikhil Bansal, Kirk Pruhs |
| 2004 | SODA | On minimizing the total flow time on multiple machines. | Nikhil Bansal |
| 2004 | SODA | New approximability and inapproximability results for 2-dimensional Bin Packing. | Nikhil Bansal, Maxim Sviridenko |
| 2004 | STOC | Approximation algorithms for deadline-TSP and vehicle routing with time-windows. | Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson |
| 2003 | ESA | Scheduling for Flow-Time with Admission Control. | Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere |
| 2003 | INFOCOM | Improving Web Performance in Broadcast-Unicast Networks. | Mukesh Agrawal, Amit Manjhi, Nikhil Bansal, Srinivasan Seshan |
| 2003 | INFOCOM | Capacity, Delay and Mobility in Wireless Ad-Hoc Networks. | Nikhil Bansal, Zhen Liu |
| 2003 | SODA | Minimizing weighted flow time. | Nikhil Bansal, Kedar Dhamdhere |
| 2003 | STOC | Server scheduling in the L | Nikhil Bansal, Kirk Pruhs |
| 2003 | STACS | Non-clairvoyant Scheduling for Minimizing Mean Slowdown. | Nikhil Bansal, Kedar Dhamdhere, Jochen Knemann, Amitabh Sinha |
| 2003 | SPAA | Online oblivious routing. | Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson |
| 2002 | FOCS | Correlation Clustering. | Nikhil Bansal, Avrim Blum, Shuchi Chawla |
| 2001 | JSSPP | SRPT Scheduling for Web Servers. | Mor Harchol-Balter, Nikhil Bansal, Bianca Schroeder, Mukesh Agrawal |
| 2001 | SIGMETRICS | Analysis of SRPT scheduling: investigating unfairness. | Nikhil Bansal, Mor Harchol-Balter |
| 1999 | ISAAC | Upper Bounds for MaxSat: Further Improved. | Nikhil Bansal, Venkatesh Raman |