38 citations · 157 across the 44 of their papers we have counts for
7 papers · 1 filter
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…
Smoothed Analysis of the Komlós Conjecture
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
The well-known Komlós conjecture states that given vectors in with Euclidean norm at most one, there always exists a coloring such that the $\ell_{\infty…
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
Nikhil Bansal, Makrand Sinha, Ronald de Wolf
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if t…