Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VECTOR BALANCING:
Reports tagged with Vector balancing:
TR26-188 | 17th September 2026
Sankeerth Rao Karingula, Shachar Lovett

An elementary proof of the Komlos conjecture

We give an elementary proof of the Komlos conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors $v_1,\ldots,v_n\in\mathbb{R}^d$ with $\|v_i\|_2\le1$ admit signs $\varepsilon_i\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i v_i\|_\infty\le36$. The proof uses only elementary combinatorial and probabilistic arguments and basic calculus.

more >>>



ISSN 1433-8092 | Imprint