3 papers
cs.DS2026
Near-Optimal Constructive Bounds for Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
Kunal Dutta, Agastya Vibhuti Jha, Haotian Jiang
A classical result of Steinitz from 1913 \cite{Ste13}, answering an earlier question of Riemann and Lévy (e.g., \cite{Lev05}), states that for any norm in $\mathbb{R}^…
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 $…