Vector balancing is the problem of assigning signs to a given collection of vectors so that their signed sum has a small prescribed vector norm. A permutation variant also allows the coordinates of each vector to be independently permuted (Niles-Weed et al. 2026).
The Komlós conjecture asks for a bound independent of the number of vectors and the dimension
when their Euclidean norms are at most 1 and the
signed sum is measured in the infinity norm. Guo
et al. (2026) report a bound less than , and Karingula and Lovett
(2026) give an elementary proof with bound 36. These statements
concern the final signed sum with signs alone.
The Beck-Fiala conjecture concerns the incidence matrix case with rows indexed by sets,
columns by elements, and bounded column sums. six
standard deviations suffice theorem gives another signing bound for matrices whose entries are
real numbers of absolute
value at most 1 (Spencer 1985).
Niles-Weed et al. (2026) proved that, for any vectors ,
, ...,
with Euclidean norm
at most 1, there are signs
and coordinate permutations
such that
where
is the infinity norm. The choices can be made online,
using only the vectors seen so far. The bound tends to
1 as
and is asymptotically optimal, since a single coordinate unit
vector forces a bound of at least 1. The result concerns the variant with permutations, not sign choices alone.