# Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method

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

## Key facts

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

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

- [Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical](https://mlsanity.com/paper/2209.01147/) (2022)

## Abstract (arXiv)

A well-known theorem of Spencer shows that any set system with n sets over n elements admits a coloring of discrepancy O(√n). While the original proof was non-constructive, recent progress brought polynomial time algorithms by Bansal, Lovett and Meka, and Rothvoss. All those algorithms are randomized, even though Bansal's algorithm admitted a complicated derandomization. We propose an elegant deterministic polynomial time algorithm that is inspired by Lovett-Meka as well as the Multiplicative Weight Update method. The algorithm iteratively updates a fractional coloring while controlling the exponential weights that are assigned to the set constraints. A conjecture by Meka suggests that Spencer's bound can be generalized to symmetric matrices. We prove that n × n matrices that are block diagonal with block size q admit a coloring of discrepancy O(√n · √log(q)). Bansal, Dadush and Garg recently gave a randomized algorithm to find a vector x with entries in lbrace-1,1rbrace with |Ax|∞ ≤ O(√log n) in polynomial time, where A is any matrix whose columns have length at most 1. We show that our method can be used to deterministically obtain such a vector.