The Komlós Conjecture

Komlós conjecture: there is an absolute constant \(C\) such that for any vectors \(v_1, \dots, v_n \in \mathbb{R}^d\) with \(\|v_i\|_2 \leq 1\), there exist signs \(\varepsilon_i \in \{\pm 1\}\) with \(\|\sum_i \varepsilon_i v_i\|_\infty \leq C\). (Best known: \(O(\sqrt{\log n})\) by Banaszczyk.)

Komlós conjectured it in the 1980s from the Beck–Fiala setting: if each column is short in Euclidean norm, the rows should balance almost perfectly. Banaszczyk (1998) proved \(O(\sqrt{\log n})\) via Gaussian measure techniques — exponentially better than trivial, yet still unbounded. The conjecture sits beside Steinitz's lemma and the Beck–Fiala and discrepancy conjectures as the central open balancing statement; a 2023 line of work (Bansal–Dadush–Garg and followers) approaches it through algorithmic discrepancy without closing the gap.