Time: Tuesday and Thursday 11:35am - 12:50pm (Zoom)
Instructor: Peng Zhang
Combinatorial discrepancy theory asks the following question: Given a ground set and a family of its subsets, how do we two-color the elements in the ground set so that the coloring is nearly balanced in every subset? One naive idea is random coloring. Our goal is to improve upon random coloring.
This course will be an introduction on combinatorial discrepancy, and will cover many of its applications. We will discuss basic concepts and classical problems, efficient algorithms developed in the last decade, and various applications. During the course, we will explore elegant tools from linear algebra, combinatorics, and probability theory.
Prerequisites
The prerequisites for this course are basic knowledge of linear algebra (at the level of MATH 222/225), probability and stochastic processes (mainly random walks, martingales, and concentration inequalities taught in STAT 251/551), and algorithm design (taught in e.g., CPSC 366).
We will not have a textbook. The basics and classical bounds are from the following books. They are available online (the first book may require VPN).
Geometric Discrepancy by Matousek
The Discrepancy Method by Chazelle
Chapter 12 of The Probabilistic Method by Alon and Spencer
The materials on efficient algorithms and applications are from recent papers.
Useful resources:
Nikolov's lecture notes in http://www.cs.toronto.edu/~anikolov/Prague18/ and http://www.cs.toronto.edu/~anikolov/csc2414.html
A STOC'20 workshop on Recent Advances in Discrepancy and Applications (organized by Bansal and Nikolov): https://www.win.tue.nl/~nikhil/disc-2020-stoc.html
Assignments
3 problem sets + paper presentation
Lecture notes:
Sep 1: [notes] Concepts of combinatorial discrepancy, matrix form, and variants
Sep 3: [notes] Two applications, random coloring and its derandomization
Sep 8: [notes] Spencer's theorem on getting sqrt(n) discrepancy (Ref: Chp 4.6 of Matousek's book or Chp 12.2 of Alon and Spencer's book, Spencer's original paper)
Sep 10: [notes] Structured set systems: Sparse set systems: the Beck-Fiala theorem (Ref: Chp 1.3 of Chazelle's book), the entropy method (Ref: Thm 5.19 in Matousek's book); Set systems of bounded VC-dimension (intro): VC-dim, shatter function (Ref: Chp 5.1, 5.2 of Matousek's book)
Sep 15: [notes] Set systems of bounded VC-dimension: a discrepancy bound better than sqrt(n) (Ref: Chp 1.4 of Chazelle's book, Chp 5.5 of Matousek's book)
Sep 17: [notes] Lower bounds: sqrt(n) discrepancy is tight (Ref: Chp 12.4 of Alon and Spencer's book); the eigenvalue bound; the determinant bound (Ref: Chp 4.3 of Matouseck's book)
Sep 22: [notes] Constructive sqrt(n) discrepancy via random walk on the edges by Lovett and Meka (Lovett and Meka's paper)
Sep 24: [notes] Constructive sqrt(n) discrepancy via convex geometry (Rothvoss's algorithm, Eldan and Singh's algorithm)
Sep 29: [notes] NP-hardness of approximating discrepancy (Charikar, Newman, Nikolov's paper)
Oct 1: Non-partial coloring algorithm for sparse set systems (Bansal, Dadush, Garg's paper, Bansal and Garg's paper)
Oct 6: [notes] Sticky Brownian rounding for CSP (paper by Abbasi-Zadeh et al., paper by Eldan and Noar)
Oct 8: [notes] Banaszczyk's theorem, equivalence to subgaussian distributions (paper by Banaszczyk, paper by Dadush, Garg, Lovett, Nikolov)
Oct 13: [notes] The Gram-Schmidt walk, an algorithm for Banaszczyk's theorem (paper by Bansal, Dadush, Garg, Lovett)
Oct 15: [notes] Randomized experimental designs using the Gram-Schmidt walk (Imbens, Rubin's book: Causal Inference for statistics, social, and biomedical sciences (via VPN), paper by Harshaw, Sävje, Spielman, Zhang, Dan's talk)
Oct 20: [notes] Random sparse set systems (paper by Ezra and Lovett)
Oct 22: [notes] Online settings (Spencer's example (page 5-7, may need VPN), algorithm by Bansal and Spencer)
Oct 27: [notes] Approximate hereditary discrepancy (paper by Matousek, Nikolov, Talwar)
Oct 29: [notes] Application of herdisc in geometry (Nikolov's lecture notes)
Nov 3: Rounding LP via discrepancy (Nikolov's lecture note)
Nov 5: [notes] Kadison-Singer problem, color rank-1 matrices (paper by Marcus, Spielman, Srivastava, their ICM survey, Terrance Tao's blog, Harvey's survey on KS and the paving conjecture)
Nov 10: [notes] KS part 2: barrier functions
Nov 12: symmetric matrix signing, invertibility and the largest eigenvalue (presented by Yihan) (paper by Carlson, Chandrasekaran, Chang, Kolla)
Nov 17: Coresets of kernel density estimation, kernel discrepancy (presented by Amar)
Nov 20: Herding, sampling from a Markov random field (presented by Yitan)
Dec 1: Application in differential privacy (presented by John)
Dec 3: Better online discrepancy algorithms (presented by Siddharth)