Vector Balancing in Polynomial Time
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))$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.23540
curl -X POST /api/v1/records/arxiv/2609.23540/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.23540/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'