Discrepancy Minimization in Input-Sparsity Time

Yichuan Deng, Xiaoyu Li, Zhao Song +1

A recent work by [Larsen, SODA 2023] introduced a faster combinatorial alternative to Bansal's SDP algorithm for finding a coloring $x\in \{-1,1{\}}^n$ that approximately minimizes…