Komlos Conjecture: the exists an absolute constant $K>0$ such that for all $d$ and any collection of vectors $v_1,\ldots, v_n\in \mathbb{R}^d$ with $\left\lVert v_i\right\rVert _2=1$ we can find weights $w_i\in\{-1,1\}$ such that $\left\lVert w_1v_1+\cdots+w_nv_n\right\rVert _{\infty}<K$.
I would like to ask what the current state of this conjecture is? Is it true that the best result towards this conjecture is that for fixed $d$ one can show the latter statement with $K=K(n)\approx \log n$?
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})$.
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.
There is a preprint just posted that claims to disprove it: https://www.preprints.org/manuscript/201902.0059/v1. They show that there is a lower bound for any n which diverges as n increases.
