CSC2414 (Fall 2015): Topics in Applied Discrete Mathmeatics

Discrepancy Theory in Computer Science

Course Information

Instructor Sasho Nikolov
Office: Sandford Fleming 2301B
E-mail:
Location Bahen 3012 (BA3012)
Time Mondays, 11am-1pm
Office hours by appointment.
Reading In addition to research papers, we will use Matousek's Geometric Discrepancy Theory. It is available online through Springer if you are on the campus network.
We will also use Chazelle's The Discrepancy Method, available from his website.
Grading Based on scribing 1-2 lectures, 2-3 problem sets, and class participation.

Course Description

Discrepancy theory is an area of mathematics that studies how well discrete objects can approximate continuous ones. This course will be an introduction to the theory, with a focus on its many applications to computer science. We will start with the basics, and move on into computational issues that arise in discrepancy theory itself. In the final part of the course we will explore applications to computational geometry, complexity theory, the design of approximation algorithms, private data analysis, and communication complexity. Along the way, we will learn about some beautiful and powerful techniques from combinatorics, linear algebra, and convex geometry.

As prerequisites, in addition to mathematical maturity, you will need basic knowledge of linear algebra and probability theory.

Scribe Notes

Use this template for your scribe notes. Do not forget to fill in the lecture number, the date, and your name. The notes should read like a self-contained text and include everything that was covered in class (rather than just record what was on the board). Please contact me if anything in the lecture you are scribing was not clear. I expect the first draft of the notes the Saturday before the meeting of the next class, so that people who have missed a lecture can look over them.

Schedule of Lectures

Find a tentative schedule of lectures below.

  1. Basic discrepancy problems: continuous discrepancy, combinatorial discrepancy, matrix discrepancy, and connections;
  2. [Lecture Notes] Geometric discrepancy: Koksma-Hlawka inequality, van der Corput construction, sketch of Roth's lower bound;
  3. [Lecture Notes] Higher-dimensional discrepancy and basics of combinatorial discrepancy: continuous discrepancy in higher dimensions, transference theorem, random colorings, the Beck-Fiala theorem;
  4. [Lecture notes] Lower bounds: eigenvalue lower bound, linear discrepancy, the determinant lower bound;
  5. [Paper] Geometric methods -- upper bounds: Giannopolous's proof of Spencer's "Six Standard Deviations Suffice" theorem, Banaszczyk's theorem;
  6. [Lecture notes] Efficient constructions: the Lovett-Meka algorithm, sketch of Rothvoss's algorithm;
  7. [Lecture notes] Computing Discrepancy: NP-hardness of approximating discrepancy, upper bound on hereditary discrepancy in terms of γ2;
  8. [Lecture notes] Lower Bound on Hereditary Discrepancy using γ2: approximation algorithm for hereditary discrepancy;
  9. [Lecture notes] Applications of γ2: properties of γ2, discrepancy of axis-aligned boxes, lower bounds on range searching data structures;
  10. [Lecture notes] Applications to approximation algorithms: LP rounding via discrepancy, approximation algorithms for bin packing and scheduling on unrelated machines;
  11. Applications to differential privacy: reconstruction attack from hereditary discrepancy, and private algorithms from γ2;