9 papers
On the Guo-Fang-Lu Algorithm for Komlos Discrepancy
Nikhil Bansal
We give an exposition of the recent polynomial time algorithm of Guo, Fang, and Lu for the Komlos problem. We simplify various arguments, and highlight the key new spectral potenti…
The Cube-Root Phenomenon in Online Carpooling
Nikhil Bansal, Milind Prabhu, Sahil Singla +1
We consider the online carpooling problem, where edges arrive online and must be oriented immediately while keeping the discrepancy between the indegree and outdegree at each verte…
Efficient Algorithms for Subdeterminant Maximization under Partition Matroids
Nikhil Bansal, Yuze Xu
We consider the determinant maximization problem under partition constraints: Given an PSD matrix A and a partition matroid on , find a base of that ma…
An Exposition of the Bound for the Komlós Problem
Nikhil Bansal, Haotian Jiang
A conjecture of Komlós states that the combinatorial discrepancy of any matrix whose columns have Euclidean norm at most one is bounded by a universal c…
Discrepancy Theory: An Algorithmic and Geometric Perspective
Nikhil Bansal, Aleksandar Nikolov
Combinatorial discrepancy theory is a subject with roots in combinatorics, geometry, and number theory, and with numerous applications to mathematics and computer science. At its c…
Online Graph Balancing and the Power of Two Choices
Nikhil Bansal, Milind Prabhu, Sahil Singla +1
In the classic online graph balancing problem, edges arrive sequentially and must be oriented immediately upon arrival, to minimize the maximum in-degree. For adversarial arrivals,…
Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
Nikhil Bansal, Haotian Jiang
The Beck-Fiala Conjecture [Discrete Appl. Math, 1981] asserts that any set system of elements with degree has combinatorial discrepancy . A substantial general…
An Improved Bound for the Beck-Fiala Conjecture
Nikhil Bansal, Haotian Jiang
In 1981, Beck and Fiala [Discrete Appl. Math, 1981] conjectured that given a set system with degree at most (i.e., each column of has at most $…
Quasi-Monte Carlo Beyond Hardy-Krause
Nikhil Bansal, Haotian Jiang
The classical approaches to numerically integrating a function are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate and have…