# Factorization Norms and Hereditary Discrepancy

arXiv: https://arxiv.org/abs/1408.1376 · HTML: https://mlsanity.com/paper/1408.1376/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2014.

## Built on by (most cited first, 14 of 14)

- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy](https://mlsanity.com/paper/2404.16706/) (2024)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [Omnipredictors for Regression and the Approximate Rank of Convex Functions](https://mlsanity.com/paper/2401.14645/) (2024)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting](https://mlsanity.com/paper/2509.14334/) (2025)
- [Learning Rate Scheduling with Matrix Factorization for Private Training](https://mlsanity.com/paper/2511.17994/) (2025)
- [Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batches](https://mlsanity.com/paper/2406.02716/) (2024)
- [Denoising the US Census: Succinct Block Hierarchical Regression](https://mlsanity.com/paper/2603.10099/) (2026)
- [The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting](https://mlsanity.com/paper/2607.00876/) (2026)
- [Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention](https://mlsanity.com/paper/2608.28150/) (2026)
- [Optimality of Matrix Mechanism on ℓpp-metric](https://mlsanity.com/paper/2406.02140/) (2024)
- [Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization](https://mlsanity.com/paper/2601.02257/) (2026)

## Abstract (arXiv)

The γ2 norm of a real m× n matrix A is the minimum number t such that the column vectors of A are contained in a 0-centered ellipsoid Esubseteqℝm which in turn is contained in the hypercube [-t, t]m. We prove that this classical quantity approximates the hereditary discrepancy herdisc A as follows: γ2(A) = O(log m)· herdisc A and herdisc A = O(√log m,)·γ2(A) . Since γ2 is polynomial-time computable, this gives a polynomial-time approximation algorithm for hereditary discrepancy. Both inequalities are shown to be asymptotically tight. We then demonstrate on several examples the power of the γ2 norm as a tool for proving lower and upper bounds in discrepancy theory. Most notably, we prove a new lower bound of Omega(logd-1 n) for the d-dimensional Tusn'ady problem, asking for the combinatorial discrepancy of an n-point set in ℝd with respect to axis-parallel boxes. For d>2, this improves the previous best lower bound, which was of order approximately log(d-1)/2n, and it comes close to the best known upper bound of O(logd+1/2n), for which we also obtain a new, very simple proof.