6 papers · 1 filter
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,…