# Algorithmic Discrepancy Beyond Partial Coloring

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

## Key facts

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

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

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance](https://mlsanity.com/paper/2504.11299/) (2025)

## Abstract (arXiv)

The partial coloring method is one of the most powerful and widely used method in combinatorial discrepancy problems. However, in many cases it leads to sub-optimal bounds as the partial coloring step must be iterated a logarithmic number of times, and the errors can add up in an adversarial way. We give a new and general algorithmic framework that overcomes the limitations of the partial coloring method and can be applied in a black-box manner to various problems. Using this framework, we give new improved bounds and algorithms for several classic problems in discrepancy. In particular, for Tusnady's problem, we give an improved O(log2 n) bound for discrepancy of axis-parallel rectangles and more generally an Od(logdn) bound for d-dimensional boxes in ℝd. Previously, even non-constructively, the best bounds were O(log2.5 n) and Od(logd+0.5n) respectively. Similarly, for the Steinitz problem we give the first algorithm that matches the best known non-constructive bounds due to Banaszczyk [Banaszczyk 2012] in the ℓ_∞ case, and improves the previous algorithmic bounds substantially in the ℓ2 case. Our framework is based upon a substantial generalization of the techniques developed recently in the context of the Koml'os discrepancy problem [BDG16].