3 papers
cs.DS2026
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,…
math.CO2025
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…
math.CO2025
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 $…