About

Nikhil Bansal is the Patrick C. Fischer Professor of Theoretical Computer Science at the University of Michigan. He is a professor in the Electrical Engineering and Computer Science Department and serves as the Director of the Theory of Computation Lab. His research interests include algorithms, optimization, machine learning, and discrete mathematics. Bansal's work focuses on theoretical aspects of computer science, contributing to the understanding and development of algorithms and mathematical frameworks that underpin computational processes.

Research topics

• Mathematics
• Computer science
• Combinatorics
• Discrete mathematics
• Algorithm

Selected publications

• Quasi-Monte Carlo Beyond Hardy-Krause

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01 · 1 citations

  book-chapter1st authorCorresponding

  We examine the problem of numerically estimating the integral of a function f. The classical approaches to this problem are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error , where σ(f ) is the standard deviation of f. QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma- Hlawka inequality, they have error Õ (σHK(f )/n ), where σΗΚ(f ) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.

  PublisherDOI

• Efficient Distributed MLLM Training with Cornstarch

  arXiv (Cornell University) · 2025-03-14

  preprintOpen access

  Multimodal large language models (MLLMs) extend the capabilities of large language models (LLMs) by combining heterogeneous model architectures to handle diverse modalities like images and audio. However, this inherent heterogeneity in MLLM model structure and data types makes makeshift extensions to existing LLM training frameworks unsuitable for efficient MLLM training. While there are a few works that have attempted to address the heterogeneity in MLLM training, their approaches are limited to only superficially considering the characteristics of MLLMs. In this paper, we present Cornstarch, an efficient distributed MLLM training framework that contemplates MLLM's unique characteristics in both model and data parallelization. Cornstarch introduces frozen-aware pipeline parallelism and token workload-balanced context parallelism to improve MLLM training throughput. Our extensive evaluation shows that Cornstarch outperforms state-of-the-art solutions by $2.26\times$ on average in terms of MLLM training throughput. Cornstarch is an open-source project available at https://github.com/cornstarch-org/Cornstarch.

  PublisherOA PDFDOI

• Introduction: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023 Special Issue

  ACM Transactions on Algorithms · 2025-06-11

  article1st authorCorresponding

  No abstract available.

  PublisherDOI

• Optimal 4-Approximation for the Correlated Pandora's Problem

  ArXiv.org · 2025-09-21

  preprintOpen access1st authorCorresponding

  The Correlated Pandora's Problem posed by Chawla et al. (2020) generalizes the classical Pandora's Problem by allowing the numbers inside the Pandora's boxes to be correlated. It also generalizes the Min Sum Set Cover problem, and is related to the Uniform Decision Tree problem. This paper gives an optimal 4-approximation for the Correlated Pandora's Problem, matching the lower bound of 4 from Min Sum Set Cover.

  PublisherOA PDFDOI

• Realtime Rendering: Simulating the Ocean with Shaders

  2025-08-01

  article

  Simulating realistic ocean scenes in real-time rendering involves balancing computational efficiency, physical accuracy, and visual appeal. Creating believable wave motion, dynamic lighting, and responsive foam effects calls for a method that carefully weighs performance against aesthetic detail. In this work, we present a shader-based framework that takes advantage of WebGPU's features for browser-based applications. We use mathematical wave models such as Gerstner waves and the Fast Fourier Transform (FFT) to mimic the dynamics of ocean surfaces without demanding heavy computation. Our comparative analysis shows that this approach achieves high frame rates while maintaining visual quality that closely resembles natural ocean behavior. The experimental results reveal significant gains in rendering speed, lower latency, and consistent performance across different hardware setups, overcoming some of the challenges seen in traditional methods. By making use of WebGPU's direct access to GPU resources, we also detail effective practices for memory management, parallel processing, and shader execution in real-time settings. Our method is versatile enough to fit various rendering pipelines, making it suitable for both desktop and mobile platforms. Overall, this study lays the groundwork for further improvements in real-time ocean rendering, helping to bring high-quality water simulations to the open web.

  PublisherDOI

• An Improved Bound for the Beck-Fiala Conjecture

  ArXiv.org · 2025-08-03

  preprintOpen access1st authorCorresponding

  In 1981, Beck and Fiala [Discrete Appl. Math, 1981] conjectured that given a set system $A \in \{0,1\}^{m \times n}$ with degree at most $k$ (i.e., each column of $A$ has at most $k$ non-zeros), its combinatorial discrepancy $\mathsf{disc}(A) := \min_{x \in \{\pm 1\}^n} \|Ax\|_\infty$ is at most $O(\sqrt{k})$. Previously, the best-known bounds for this conjecture were either $O(k)$, first established by Beck and Fiala [Discrete Appl. Math, 1981], or $O(\sqrt{k \log n})$, first proved by Banaszczyk [Random Struct. Algor., 1998]. We give an algorithmic proof of an improved bound of $O(\sqrt{k \log\log n})$ whenever $k \geq \log^5 n$, thus matching the Beck-Fiala conjecture up to $O(\sqrt{\log \log n})$ for almost the full regime of $k$.

  PublisherOA PDFDOI

• Pseudorandom quantum authentication

  arXiv (Cornell University) · 2025-01-01

  preprintOpen access

  We introduce the pseudorandom quantum authentication scheme (PQAS), an efficient method for encrypting quantum states that relies solely on the existence of pseudorandom unitaries (PRUs). The scheme guarantees that for any eavesdropper with quantum polynomial-time (QPT) computational power, the encrypted states are indistinguishable from the maximally mixed state. Furthermore, the receiver can verify that the state has not been tampered with and recover the original state with asymptotically unit fidelity. Our scheme is cost-effective, requiring only polylogarithmic circuit depth and a single shared key to encrypt a polynomial number of states. Notably, the PQAS can potentially exist even without quantum-secure one-way functions, requiring fundamentally weaker computational assumptions than semantic classical cryptography. Additionally, PQAS is secure against attacks that plague protocols based on QPT indistinguishability from Haar random states, such as chosen-plaintext attacks (CPAs) and attacks that reveal meta-information such as quantum resources. We relate the amount of meta-information that is leaked to quantum pseudoresources, giving the concept a practical meaning. As an application, we construct important cryptographic primitives, such as verifiable pseudorandom density matrices (VPRDMs), which are QPT-indistinguishable from random mixed states while being efficiently verifiable via a secret key, as well as verifiable noise-robust EFI pairs and one-way state generators (OWSGs). Our results establish a new paradigm of quantum information processing with weaker computational assumptions.

  PublisherOA PDFDOI

• Pseudorandom Density Matrices

  PRX Quantum · 2025-05-01 · 10 citations

  articleOpen access1st authorCorresponding

  Pseudorandom states (PRSs) are state ensembles that cannot be efficiently distinguished from Haar-random states. However, the definition of PRSs has been limited to pure states and lacks robustness against noise. In this work, we introduce pseudorandom density matrices (PRDMs), ensembles of <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><a:mi>n</a:mi></a:math>-qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble (GHSE), which is constructed from <d:math xmlns:d="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><d:mo stretchy="false">(</d:mo><d:mi>n</d:mi><d:mo>+</d:mo><d:mi>m</d:mi><d:mo stretchy="false">)</d:mo></d:math>-qubit Haar random states with <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><i:mi>m</i:mi></i:math> qubits traced out. For <l:math xmlns:l="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><l:mi>m</l:mi><l:mo>=</l:mo><l:mn>0</l:mn></l:math>, PRDMs are equivalent to PRSs, whereas for <o:math xmlns:o="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><o:mi>m</o:mi><o:mo>=</o:mo><o:mi>ω</o:mi><o:mo stretchy="false">(</o:mo><o:mi>log</o:mi><o:mo></o:mo><o:mi>n</o:mi><o:mo stretchy="false">)</o:mo></o:math>, PRDMs are computationally indistinguishable from the maximally mixed state. PRDMs with <t:math xmlns:t="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><t:mi>m</t:mi><t:mo>=</t:mo><t:mi>ω</t:mi><t:mo stretchy="false">(</t:mo><t:mi>log</t:mi><t:mo></t:mo><t:mi>n</t:mi><t:mo stretchy="false">)</t:mo></t:math> are robust to unital noise channels and separated in terms of security from PRS. PRDMs can disguise valuable quantum resources as trivial states. In particular, we construct pseudoresource state ensembles, which possess near-maximal entanglement, magic and coherence, but are computationally indistinguishable from resource-free states. PRDMs exhibit a pseudoresource gap of <y:math xmlns:y="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><y:mi mathvariant="normal">Θ</y:mi><y:mo stretchy="false">(</y:mo><y:mi>n</y:mi><y:mo stretchy="false">)</y:mo></y:math> vs 0, surpassing previously found gaps. We also render EFI pairs, a fundamental cryptographic primitive, robust to strong mixed unitary noise. Our work has major implications on quantum resource theory. We show that entanglement, magic, and coherence cannot be efficiently tested, and that black-box resource distillation requires a superpolynomial number of copies. We also establish lower bounds on the purity needed for efficient testing and black-box distillation. Finally, we introduce memoryless PRSs, a noise-robust notion of PRS, which are indistinguishable to Haar random states for efficient algorithms without quantum memory, as well as noise-robust quantum money. Our work provides a comprehensive framework of pseudorandomness for mixed states, which yields powerful quantum cryptographic primitives and fundamental bounds on quantum resource theories.

  PublisherOA PDFDOI

• Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds

  arXiv (Cornell University) · 2024-05-02

  preprintOpen access1st authorCorresponding

  Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as $k$-means. Given a point set $P$, a coreset $Ω$ is a small, weighted summary that preserves the cost of all candidate solutions $S$ up to a $(1\pm \varepsilon)$ factor. For $k$-means in $d$-dimensional Euclidean space the cost for solution $S$ is $\sum_{p\in P}\min_{s\in S}\|p-s\|^2$. A very popular method for coreset construction, both in theory and practice, is Sensitivity Sampling, where points are sampled in proportion to their importance. We show that Sensitivity Sampling yields optimal coresets of size $\tilde{O}(k/\varepsilon^2\min(\sqrt{k},\varepsilon^{-2}))$ for worst-case instances. Uniquely among all known coreset algorithms, for well-clusterable data sets with $Ω(1)$ cost stability, Sensitivity Sampling gives coresets of size $\tilde{O}(k/\varepsilon^2)$, improving over the worst-case lower bound. Notably, Sensitivity Sampling does not have to know the cost stability in order to exploit it: It is appropriately sensitive to the clusterability of the data set while being oblivious to it. We also show that any coreset for stable instances consisting of only input points must have size $Ω(k/\varepsilon^2)$. Our results for Sensitivity Sampling also extend to the $k$-median problem, and more general metric spaces.

  PublisherOA PDFDOI

• The Power of Two Choices in Graphical Allocation

  SIAM Journal on Computing · 2024-08-26

  article1st authorCorresponding
  PublisherDOI

Recent grants

• Collaborative Research: AF: Small: New Directions and Approaches in Discrepancy Theory

  NSF · $300k · 2023–2026

Frequent coauthors

• Kirk Pruhs

  University of Pittsburgh

  38 shared

• Viswanath Nagarajan

  Karpagam Academy of Higher Education

  30 shared

• Ho-Leung Chan

  University of Hong Kong

  23 shared

• Don Coppersmith

  23 shared

• Shashwat Garg

  23 shared

• Anupam Gupta

  Mercer University

  19 shared

• Maria-Florina Balcan

  18 shared

• Alina Beygelzimer

  Research!America (United States)

  18 shared