Elementary proof shows balanced sign choices keep vectors small
An elementary proof of the Komlós conjecture
Computational Complexity
Summary
The paper solves a problem about balancing numbers attached to points in space so that when added up with plus or minus signs, their largest coordinate stays small. The authors provide an easier and more straightforward demonstration than before, showing that for any set of points within a unit size, it's always possible to pick plus or minus signs so their combined effect is limited by a specific number. The proof only uses basic math tools like elementary counting and probability, making it accessible and simpler.
What this means in practice
- •For optimization algorithm designers: Use the elementary bound on vector sums to improve algorithm guarantees involving signed vector combinations.
- •For signal processing engineers: Design methods to balance signals represented as vectors for reduced peak magnitude using the bound on signed vector sums.
A theory result. No direct application yet.
Authors
Sankeerth Rao Karingula, Shachar Lovett
Abstract
We give an elementary proof of the Komlós 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.