Fetching the paper…
Reading the bibliography…
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 the discrepancy $\mathrm{disc}(A, x) := | A x |_{\infty}$ of a real-valued $m \times n$ matrix $A$.
On the uniform convergence of relative frequencies of events to their probabilities
VN Vapnik and A Ya Chervonenkis · 1971
Earlier work this paper cites.
“integer-making” theorems
József Beck and Tibor Fiala · 1981
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
Six standard deviations suffice
Joel Spencer · 1985
Earlier work this paper cites.
Discrepancy of set-systems and matrices
László Lovász, Joel Spencer, and Katalin Vesztergombi · 1986
Earlier work this paper cites.
Concentration of measure and isoperimetric inequalities in product spaces
Michel Talagrand · 1995
Earlier work this paper cites.
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1996
Earlier work this paper cites.
Balancing vectors and gaussian measures of n-dimensional convex bodies
Wojciech Banaszczyk · 1998
Earlier work this paper cites.
Geometric discrepancy: An illustrated guide
Jiri Matousek · 1999
Earlier work this paper cites.
The discrepancy method: randomness and complexity
Bernard Chazelle · 2000
Earlier work this paper cites.
Computational geometry: algorithms and applications
Mark De Berg · 2000
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2002
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamas Sarlos · 2006
Earlier work this paper cites.
Constructive algorithms for discrepancy minimization
Nikhil Bansal · 2010
Earlier work this paper cites.
Tight hardness results for minimizing discrepancy
Moses Charikar, Alantha Newman, and Aleksandar Nikolov · 2011
Earlier work this paper cites.
A variant of azuma’s inequality for martingales with subgaussian tails
Ohad Shamir · 2011
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
Improved analysis of the subsampled randomized hadamard transform
Joel A Tropp · 2011
Earlier work this paper cites.
Semidefinite optimization in discrepancy theory
Nikhil Bansal · 2012
Earlier work this paper cites.
Twice-ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Earlier work this paper cites.
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, and David P Woodruff · 2012
Earlier work this paper cites.
Optimal private halfspace counting via discrepancy
Shanmugavelayutham Muthukrishnan and Aleksandar Nikolov · 2012
Earlier work this paper cites.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Earlier work this paper cites.
Algebraic complexity theory
Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi · 2013
Earlier work this paper cites.
Fast matrix multiplication
Markus Bläser · 2013
Earlier work this paper cites.
Low rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 2013
Earlier work this paper cites.
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2013
Earlier work this paper cites.
The geometry of differential privacy: the sparse and approximate cases
Aleksandar Nikolov, Kunal Talwar, and Li Zhang · 2013
Earlier work this paper cites.
Approximating bin packing within O(log(OPT) loglog(OPT)) bins
Thomas Rothvoß · 2013
Earlier work this paper cites.
Path finding methods for linear programming: Solving linear programs in O ( r a n k \sqrt{rank} ) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Earlier work this paper cites.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Earlier work this paper cites.
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak · 2015
Cited alongside, same era.
Constructive discrepancy minimization by walking on the edges
Shachar Lovett and Raghu Meka · 2015
Cited alongside, same era.
Randomized rounding for the largest simplex problem
Aleksandar Nikolov · 2015
Cited alongside, same era.
An introduction to matrix concentration inequalities
Joel A Tropp et al · 2015
Cited alongside, same era.
Optimal principal component analysis in distributed and streaming models
Christos Boutsidis, David P Woodruff, and Peilin Zhong · 2016
Cited alongside, same era.
Nearly tight oblivious subspace embeddings by trace inequalities
Michael B Cohen · 2016
A faster interior point method for semidefinite programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song · 2020
Later among the works it cites.
A faster interior point method for semidefinite programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song · 2020
Later among the works it cites.
An improved cutting plane method for convex optimization, convex-concave games, and its applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong · 2020
Later among the works it cites.
Discrepancy minimization via a self-balancing walk
Ryan Alweiss, Yang P Liu, and Mehtaab Sawhney · 2021
Later among the works it cites.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2021
Later among the works it cites.
Training (overparametrized) neural networks in near-linear time
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein · 2021
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Ramanujan graphs in polynomial time
Michael B Cohen · 2016
Cited alongside, same era.
Weighted low rank approximations with provable guarantees
Ilya Razenshteyn, Zhao Song, and David P Woodruff · 2016
Cited alongside, same era.
A logarithmic additive integrality gap for bin packing
Rebecca Hoberg and Thomas Rothvoss · 2017
Cited alongside, same era.
Constructive discrepancy minimization with hereditary l2 guarantees
Kasper Green Larsen · 2017
Cited alongside, same era.
Optimality of the johnson-lindenstrauss lemma
Kasper Green Larsen and Jelani Nelson · 2017
Cited alongside, same era.
Faster online matrix-vector multiplication
Kasper Green Larsen and Ryan Williams · 2017
Cited alongside, same era.
Later among the works it cites.
Faster dynamic matrix inverse for faster lps
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang · 2021
Later among the works it cites.
Oblivious sketching-based central path method for linear programming
Zhao Song and Zheng Yu · 2021
Later among the works it cites.
A unified approach to discrepancy minimization
Nikhil Bansal, Aditi Laddha, and Santosh S Vempala · 2022
Closest in time.
Information discrepancy in strategic learning
Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani · 2022
Closest in time.
A faster small treewidth sdp solver
Yuzhou Gu and Zhao Song · 2022
Closest in time.
Solving sdp faster: A robust ipm framework and efficient implementation
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang · 2022
Closest in time.
Solving sdp faster: A robust ipm framework and efficient implementation
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang · 2022
Closest in time.
Training overparametrized neural networks in sublinear time
Hang Hu, Zhao Song, Omri Weinstein, and Danyang Zhuo · 2022
Closest in time.
Accelerating frank-wolfe algorithm using low-dimensional and adaptive data structures
Zhao Song, Zhaozhuo Xu, Yuanyuan Yang, and Lichen Zhang · 2022
Closest in time.
Speeding up sparsification with inner product search data structures
Zhao Song, Zhaozhuo Xu, and Lichen Zhang · 2022
Closest in time.
Speeding up optimizations via data structures: Faster search, sample and maintenance
Lichen Zhang · 2022
Closest in time.
Attention scheme inspired softmax regression
Yichuan Deng, Zhihang Li, and Zhao Song · 2023
Closest in time.
An iterative algorithm for rescaled hyperbolic functions regression
Yeqi Gao, Zhao Song, and Junze Yin · 2023
Closest in time.
Spencer’s theorem in nearly input-sparsity time
Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney · 2023
Closest in time.
Fast discrepancy minimization with hereditary guarantees
Kasper Green Larsen · 2023
Closest in time.
Solving regularized exp, cosh and sinh regression problems
Zhihang Li, Zhao Song, and Tianyi Zhou · 2023
Closest in time.
Discrepancy minimization via regularization
Lucas Pesenti and Adrian Vladu · 2023
Closest in time.
An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization
Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo · 2023
Closest in time.
Sketching meets differential privacy: Fast algorithm for dynamic kronecker projection maintenance
Zhao Song, Xin Yang, Yuanyuan Yang, and Lichen Zhang · 2023
Closest in time.
Algorithm and hardness for dynamic attention maintenance in large language models
Jan van den Brand, Zhao Song, and Tianyi Zhou · 2024
Closest in time.
Linear-sized sparsifiers via near-linear time discrepancy theory
Arun Jambulapati, Victor Reis, and Kevin Tian · 2024
Closest in time.
A tighter complexity analysis of sparsegpt
Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song · 2024
Closest in time.
New bounds for matrix multiplication: from alpha to omega
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou · 2024
Closest in time.
More asymmetry yields faster matrix multiplication
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou · 2025
Closest in time.