Komlós conjectured that for any matrix $A\in\mathbb R^{m\\times n}$ whose columns all have Euclidean norm at most one, the combinatorial discrepancy of $A$ is bounded by a universal constant independent of dimensions. We show that every such matrix satisfies $$ \text{disc}(A) \le C\, (\log n)^{1/4}(\log\log n)^{7/4}, $$\nwhere $C$ is an absolute constant. This result is the first asymptotic improvement over the $O(\sqrt{\log n})$ bound proved by Banaszczyk in 1998, and it disproves Hajela’s 1988 conjecture that a lower bound of order $\Omega(\sqrt{\log n})$ should hold.
The proof combines balancing techniques for random processes with volume estimates in high‑dimensional geometry. One starts by sampling a Gaussian vector $g\sim\mathcal N(0,I_m)$ and examining its projection onto the column space of $A$. Using Banaszczyk’s vector balancing lemma, the projection error can be kept within $O(\sqrt{\log n})$. A careful block decomposition together with a recursive reduction scheme then shrinks the error further to the $(\log n)^{1/4}(\log\log n)^{7/4}$ scale. The essential idea is to apply fine‑grained bias correction at each recursion level so that the accumulated error decays sub‑square‑rootly.
The emergence of this bound suggests that the true growth rate of combinatorial discrepancy may be far lower than previously believed, and it provides new tools for future work, such as refined random projections and hierarchical balancing methods.
Blogger's Review: This paper makes a striking advance at the intersection of discrete geometry and random analysis, raising the upper bound while overturning a long‑standing lower‑bound conjecture, and it offers techniques that merit close study and further development.