Graduate Seminar on Algorithms and Optimization (S4C3): Discrepancy Theory
Discrepancy theory is a highly active subfield of discrete mathematics with broad applications in computer science. The basic question here is whether we can two-color the elements of a given set system in such a way that every set contains roughly an equal number of elements from each color class and performs better than the oblivious random coloring.
The earliest solution of this problem was found by Beck and Fiala in 1981 who gave an algorithm to efficiently find such low-discrepancy colorings using simple linear algebraic methods and then by Joel Spencer in 1985 who gave a non-constructive existential proof (in a different setting) using partial coloring methods.
Since then, different research directions have emerged. We will focus on three of them:
The earliest solution of this problem was found by Beck and Fiala in 1981 who gave an algorithm to efficiently find such low-discrepancy colorings using simple linear algebraic methods and then by Joel Spencer in 1985 who gave a non-constructive existential proof (in a different setting) using partial coloring methods.
Since then, different research directions have emerged. We will focus on three of them:
- How to design efficient algorithms for those originally non-constructive approaches, like Spencer's and Banaszczyk's
- Discrepancy problems in other settings, like the matrix version (quantum distribution v.s. classic), designing online algorithms and smooth analysis.
- Application of the discrepancy results, like LP-rounding, sparsification and faster integration (geometric discrepancy).
We aim in this seminar to give an overview of different discrepancy problems and the currently available techniques for attacking them.
Interested students are encouraged to contact Matthias Kaul at mkaul@uni-bonn.de. Students who cannot attend the planning meeting can still sign up by sending an email.
Dates
Pre-meeting:
Thursday, 17th July, 2025, 18:00,
Gerhard-Konow-Hörsaal, Lennéstr. 2
Class hours:
Monday 14:15-15:45. Approval talks: 16:15-17:45
Rules and Regulations
- Seminars will be held Monday 14:15-15:45, with approval talks on the same days 16:15-17:45.
- A regular participation in the talks and an active collaboration are mandatory for passing the seminar
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.
Literature
- "Integer-making" theorem (Beck, Fiala, '81)
- Six standard deviations suffice (Joel Spencer, '85)
- Balancing vectors and Gaussian measures of n-dimensional convex bodies (Wojciech Banaszczyk, '98)
- Flow Time Scheduling and Prefix Beck-Fiala (Bansal, Rohwedder, Svensson, '22)
- Better bin packing approximations via discrepancy theory (Thomas Rothvoss, '16)
- Constructive discrepancy minimization by walking on the edges (Lovett, Meka, '15)
- Constructive discrepancy minimization for convex sets (Thomas Rothvoss, '17)
- The Gram–Schmidt walk: a cure for the Banaszczyk blues (Bansal, Dadush, Garg, Lovett, '19)
- A Unified Approach to Discrepancy Minimization (Bansal, Laddha, Vempala, '22)
- Optimal Online Discrepancy Minimization (Kulkarni, Reis, Rothvoss, '24)
- Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing (Bansal, Jiang, Meka, Singla, Sinha, '22)
- Quasi-Monte Carlo Beyond Hardy-Krause (Bansal, Jiang, '25)
- Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank (Bansal, Jiang, Meka, '23)
- Interlacing families II: mixed characteristic polynomials and the Kadison–Singer problem (Marcus, Spielman, Srivastava, '15)