Discrepancy Minimization in Input-Sparsity Time

A recent work by [Larsen, SODA 2023] introduced a faster combinatorial alternative to Bansal's SDP algorithm for finding a coloring x ∈ -1, 1 n that approximately minimizes the discrepancy disc(A, x) := |Ax| ∞ of a real-valued m × n matrix A. Larsen's algorithm runs in O(mn 2 ) time compared to Bansal's O(mn 4.5 )-time algorithm, with a slightly weaker logarithmic approximation ratio in terms of the hereditary discrepancy of A [Bansal, FOCS 2010]. We present a combinatorial O(nnz(A) + n 3 )-time algorithm with the same approximation guarantee as Larsen's, optimal for tall matrices where m = poly(n). Using a more intricate analysis and fast matrix multiplication, we further achieve a runtime of O(nnz(A) + n 2.53 ), breaking the cubic barrier for square matrices and surpassing the limitations of linear-programming approaches [Eldan and Singh, RS&A 2018]. Our algorithm relies on two key ideas: (i) a new sketching technique for finding a projection matrix with a short ℓ 2 -basis using implicit leverage-score sampling, and (ii) a data structure for efficiently implementing the iterative Edge-Walk partialcoloring algorithm [Lovett and Meka, SICOMP 2015], and using an alternative analysis to enable "lazy" batch updates with low-rank corrections. Our results nearly close the computational gap between real-valued and binary matrices, for which input-sparsity time coloring was recently obtained by [Jain, Sah and Sawhney, SODA 2023].