Fast Spectral Signing for Vector Balancing

Abstract

The Komlós conjecture, now a theorem, asks for a constant-discrepancy signing of every matrix whose columns have Euclidean norm at most one. We give a deterministic spectral-signing algorithm that returns signs ε ∈ {−1, 1}^n satisfying ‖Aε‖∞ < 99. It uses O(n² log n) fractional-coloring updates and O(mn + n^(ω+2) log³n) arithmetic operations and comparisons for any fixed attainable matrix-multiplication exponent ω > 2. The implementation replaces the costly steps in previous spectral signing with short sequences of matrix products, while energy-corrected barriers and a motion clock ensure that only O(n log² n) rows need attention at any update. For rational input, it also has polynomial bit complexity.