An Exposition of the $\tilde{O}({\log }^{1/4}n)$ Bound for the Komlós Problem

Abstract

A conjecture of Komlós states that the combinatorial discrepancy of any matrix $A\in {\mathbb{R}}^{m\times n}$ whose columns have Euclidean norm at most one is bounded by a universal constant. We prove that the combinatorial discrepancy of every such matrix is at most $O((\log n{)}^{1/4}(\log \log n{)}^{7/4})$. This is the first asymptotic improvement over the $O(\sqrt{\log n})$ bound established by Banaszczyk [Banaszczyk, Random Struct.\ Algorithms, 1998], and it refutes a conjecture of Hajela [Hajela, European J.\ Combin., 1988] that a lower bound of order $\Omega (\sqrt{\log n})$ should hold.

An extended abstract of this work appeared in STOC 2026: https://arxiv.org/pdf/2508.03961. The present article treats only the Komlós problem; the proof is simplified and recast via stochastic calculus