The Komlós Problem in Matrix-Multiplication Time

Emile Anand, Peter Chen

We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(…