{"ID":5937736,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-08T16:25:08.048777621Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04388","arxiv_id":"2607.04388","title":"Optimal Online Discrepancy Minimization in Linear Time","abstract":"We provide an online algorithm with the following guarantee: for any fixed sequence of vectors $v_1,\\dots,v_T \\in \\mathbf{R}^d$ with $\\|v_i\\|_2\\le 1$, the algorithm assigns each arriving vector $v_t$ a random sign $\\varepsilon_t$ such that every prefix sum $\\sum_{i=1}^t \\varepsilon_i v_i $ can be written as the sum of three coupled standard Gaussian vectors. Our algorithm runs in $O(dT)$ time and achieves the optimal prefix discrepancy bound \\[ \\max_{1 \\le t \\le T}\\left\\| \\sum_{i=1}^t \\varepsilon_i v_i \\right\\|_\\infty = O\\left( \\sqrt{\\log T} \\right), \\] with high probability. This recovers the optimal bound of Kulkarni, Reis, and Rothvoss, whose algorithm runs in time exponential in $T$ and $d$. The algorithm and main proof were discovered in a GPT-5.5 Pro Extended conversation prompted by the author.","short_abstract":"We provide an online algorithm with the following guarantee: for any fixed sequence of vectors $v_1,\\dots,v_T \\in \\mathbf{R}^d$ with $\\|v_i\\|_2\\le 1$, the algorithm assigns each arriving vector $v_t$ a random sign $\\varepsilon_t$ such that every prefix sum $\\sum_{i=1}^t \\varepsilon_i v_i $ can be written as the sum of...","url_abs":"https://arxiv.org/abs/2607.04388","url_pdf":"https://arxiv.org/pdf/2607.04388v1","authors":"[\"Ishaq Aden-Ali\"]","published":"2026-07-05T16:31:42Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}