Current state of the Komlos conjecture on vector balancing

As far as I know, the state of the art is that one can actually achieve $K=K(n)=O(\log^{\frac{1}{2}} n)$ independent of the dimension $d$. Moreover, one can actually find the weights $w_i$ via an efficient randomized algorithm. This matches the best non-constructive bound due to Banaszczyk. See this paper of Bansal, Dadush and Garg.


For fixed $d$, one can actually achieve a bound independent of $n$. More precisely, $K=K(d)=O(\sqrt{d})$ is fine, uniformly in $n$.

Proof : the unit ball of $\mathbb{R}^d$ can be covered by $2C^d$ balls of radius $\frac{1}{2}$, for some absolute constant $C$. Let $v_1,\dots,v_n$ be $n$ vectors in $\mathbb{R}^d$ of norm at most $1$. If $n>2C^d$, then one can find $v_i,v_j$, for some $i<j$, belonging to the same ball of radius $\frac{1}{2}$; in particular $||v_i-v_j||_2 \leq 1$. By considering, the finite list $v_i- v_j, v_1,\dots,\hat{v_{i}},\dots,\hat{v_j}, \dots v_n$, one reduces to the case of $n-1$ vectors of norm at most $1$. Iterating this process, one reduces to the case $n \leq 2C^d$. Then one applies Banaszczyk's result to get a bound $O(\log^{\frac{1}{2}} 2C^{d}) = O(\sqrt{d})$.