RETRACTED: Constructive ℓ2-Discrepancy Minimization with Additive Deviations

The signed series problem in the $\ell_{2}$ norm asks, given a set of vectors $v_{1},\ldots,v_{n}\in\mathbb{R}^{d}$ having at most unit $\ell_{2}$ norm, does there always exist a series $(\varepsilon_{i})_{i\in[n]}$ of $\pm1$ signs such that for all $i\in[n]$, $\max_{i\in[n]}\left\|\sum_{j=1}^{i}\varepsilon_{i}v_{i}\right\|_{2}=O\left(\sqrt{d}\right)$. A result of Banaszczyk [2012, Rand. Struct. Alg.] states that there exist signs $\varepsilon_{i}\in\{-1,1\}$, $i\in[n]$ such that $\max_{i\in[n]}\left\|\sum_{j=1}^{i}\varepsilon_{i}v_{i}\right\|_{2} = O\left(\sqrt{d + \log n}\right)$. The best constructive bound known so far is $O\left(\sqrt{d\log n}\right)$, by Bansal and Garg [2017, STOC, 2019, SIAM J. Comput.]. We give a polynomial-time randomized algorithm to find signs $x(i)\in\{-1,1\}$, $i\in[n]$ such that $\max_{i\in[n]}\|\sum_{j=1}^{i}x(i)v_{i}\|_{2} = O\left(\sqrt{d + \log n}\right) = O\left(\sqrt{d} + \sqrt{\log n}\right)$. By the constructive reduction of Harvey and Samadi [COLT, 2014], this also yields a constructive bound of $O\left(\sqrt{d} + \sqrt{\log n}\right)$ for the Steinitz problem in the $\ell_{2}$-norm, where the conjectured bound is also $O\left(\sqrt{d}\right)$. Thus, we algorithmically achieve Banaszczyk’s bounds for both problems, which also matches the conjectured bounds.