{"id":"arxiv/2609.23540","url":"https://arxiv.org/abs/2609.23540","tags":["cs.DS","math.CO"],"score":0,"title":"Vector Balancing in Polynomial Time","domain":"cs.DS","source":"arxiv","authors":["Shengtao Guo","Ethan X. Fang","Junwei Lu"],"reviews":0,"subject":"cs.DS","summary":"We present a spectral signing algorithm solving the Komlós problem with a constant discrepancy in polynomial time. Given a matrix $A\\in\\mathbb{R}^{m\\times n}$ whose columns have Euclidean norm at most $1$, the algorithm finds a vector $\\varepsilon\\in\\{-1,1\\}^n$ satisfying $\\|A\\varepsilon\\|_\\infty\\le C$, where $C$ is an absolute constant. By minimizing a cubic spectral potential, our spectral signing algorithm updates the fractional coloring toward Boolean signs with time complexity $O((mn^9+n^{10})\\log(2+m+n))$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}