Lune

ICML2025Top-tier venue

Discrepancy Minimization in Input-Sparsity Time

Yichuan Deng, Xiaoyu Li, Zhao Song, Omri Weinstein

Abstract

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].

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • A Faster Interior Point Method for Semidefinite Programming cites Solving tall dense linear programs in nearly linear time
  • Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation cites Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
  • Convex Minimization with Integer Minima in Õ(n4) Time cites Solving tall dense linear programs in nearly linear time
  • Convex Minimization with Integer Minima in Õ(n4) Time cites A Faster Interior Point Method for Semidefinite Programming
  • Convex Minimization with Integer Minima in Õ(n4) Time cites Faster Algorithms for Structured John Ellipsoid Computation
  • Convex Minimization with Integer Minima in Õ(n4) Time cites New Bounds for Matrix Multiplication: from Alpha to Omega
  • Faster Algorithms for Structured John Ellipsoid Computation cites Solving tall dense linear programs in nearly linear time
  • Faster Algorithms for Structured John Ellipsoid Computation cites A Faster Interior Point Method for Semidefinite Programming
  • Faster Algorithms for Structured John Ellipsoid Computation cites Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
  • Faster Algorithms for Structured John Ellipsoid Computation cites A Refined Laser Method and Faster Matrix Multiplication
  • Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance cites Solving tall dense linear programs in nearly linear time
  • Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance cites A Faster Interior Point Method for Semidefinite Programming
  • New Bounds for Matrix Multiplication: from Alpha to Omega cites A Refined Laser Method and Faster Matrix Multiplication
  • A Refined Laser Method and Faster Matrix Multiplication cites New Bounds for Matrix Multiplication: from Alpha to Omega
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. Faster Algorithms for Structured John Ellipsoid ComputationYang Cao, Xiaoyu Li, Zhao Song, Xin Yang et al.NeurIPS 2025 · 33 citations
  2. Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection MaintenanceZhao Song, Xin Yang, Yuanyuan Yang, Lichen ZhangICML 2023 · 30 citations
  3. Convex Minimization with Integer Minima in Õ(n4) TimeHaotian Jiang, Yin Tat Lee, Zhao Song, Lichen ZhangSODA 2024 · 2 citations
  4. Efficient Alternating Minimization with Applications to Weighted Low Rank ApproximationZhao Song, Mingquan Ye, Junze Yin, Lichen ZhangICLR 2025 · 1 citation
  5. Linear-Sized Sparsifiers via Near-Linear Time Discrepancy TheoryArun Jambulapati, Victor Reis, Kevin TianSODA 2024 · 1 citation

Builds on17

  1. A Refined Laser Method and Faster Matrix MultiplicationJosh Alman, Virginia Vassilevska WilliamsSODA 2021 · 275 citations
  2. New Bounds for Matrix Multiplication: from Alpha to OmegaVirginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei ZhouSODA 2024 · 90 citations
  3. A Faster Interior Point Method for Semidefinite ProgrammingHaotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan et al.FOCS 2020 · 62 citations
  4. Solving tall dense linear programs in nearly linear timeJan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao SongSTOC 2020 · 59 citations
  5. Information Discrepancy in Strategic LearningYahav Bechavod, Chara Podimata, Zhiwei Steven Wu, Juba ZianiICML 2022 · 57 citations

Related papers

  1. Fast Discrepancy Minimization with Hereditary GuaranteesKasper Green LarsenSODA 2023
  2. Spencer's theorem in nearly input-sparsity timeVishesh Jain, Ashwin Sah, Mehtaab SawhneySODA 2023 · 1 citation
  3. Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds beyond BanaszczykNikhil Bansal, Haotian JiangSTOC 2026 · 28 citations
  4. Matrix discrepancy from Quantum communicationSamuel B. Hopkins, Prasad Raghavendra, Abhishek ShettySTOC 2022 · 8 citations
  5. A new framework for matrix discrepancy: partial coloring bounds via mirror descentDaniel Dadush, Haotian Jiang, Victor ReisSTOC 2022 · 7 citations
Dusk over the sea between two cliffs drawn in fine vertical lines