38 citations · 157 across the 44 of their papers we have counts for
46 papers · 1 filter
Hardness of A/E-Design under Partition Constraints
Nikhil Bansal, Yuze Xu
We consider the A/E-design problem under partition constraints: Given vectors and a partition matroid on , find a base of the matroid that minimiz…
On Minimizing Generalized Makespan on Unrelated Machines
Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu
We consider the Generalized Makespan Problem (GMP) on unrelated machines, where we are given jobs and machines and each job has arbitrary processing time on ma…
A Nearly Tight Lower Bound for the -Dimensional Cow-Path Problem
Nikhil Bansal, John Kuszmaul, William Kuszmaul
In the -dimensional cow-path problem, a cow living in must locate a -dimensional hyperplane whose location is unknown. The only way that the cow can…
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
Nikhil Bansal, Haotian Jiang, Raghu Meka
We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric matrices each with …
Balanced Allocations: The Heavily Loaded Case with Deletions
Nikhil Bansal, William Kuszmaul
In the 2-choice allocation problem, balls are placed into bins, and each ball must choose between two random bins that it has been assigned to. It has been k…
A Unified Approach to Discrepancy Minimization
Nikhil Bansal, Aditi Laddha, Santosh S. Vempala
We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various…