RETRACTED: Constructive \(\ell_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.