308-760A Concentration Inequalities, Fall '04

Course Info

Time & Place:
2:30-4:00 Monday and Wednesday, McConnel 320

B. Reed MC301, breed@cs.mcgill.ca
Office Hours: Wednesday 8-10
V. Jaksic Burnside 1209, jaksic@math.mcgill.ca
Office Hours: TBA

Prerequisites: Graduate Advanced Probability Course or 308-490 or 308-690.


There will be 3 homework assignments worth 50% and a presentation. worth 50%.

For a course description and list of references see:

We will mainly use McDiarmid's survey. and Lugosi's survey.

Thanks also to Shannon Starr for getting us a copy of A paper by Talagrand.

Lecture 1, September 1: Introduction and Chernoff Bounds Sections 1-3 of Lugosi and Section 2 of McDiarmid.

Lecture 2, September 8: The Chromatic Number of G(n,p) Section 5.1 of Molloy and Reed (handed out in class) and Section 3.1.2 of McDiarmid (plus references there)

Lecture 3, September 13: Efron-Stein and its Applications Section 4 of Lugosi

Lecture 4, September 15: The Bounded Differences Inequality Section 5.1-5.4 of Lugosi

Lecture 5, September 20: Combinatorial Entropies and the Lovasz Local Lemma. Rest of Section 5 of Lugosi, LLL reference yet to be determined, Assignment 2 handed out.

Lecture 6, October 4: Another Graph Colouring Application (Student Presentation) Chapter X of Molloy and Reed for an unknown $X$, Assignment 1 due.

Lecture 7, October 6: Martingales, Section 3.3-3.6 of McDiarmid

Lecture 8, October 13: An application to hypergraph matchings. Section 3.2.1 of McD and references there.

Lecture 9, October 18: Isoperimetric Inequalities, Section 3.1.3 of MCD and the section beginning on page 18 of MCD on permutation graphs

Lecture 9, October 20: Talagrand I, Section 4 of McDiarmid

Lecture 10, October 25: More on Talagrand and taking up assignment 1.

Lecture 11, October 27th: Random Polynomial, Ketan

Lecture 12, Nov 3rd: Taking up assignment II.

Lecture 13, Nov 5th, VC Dimension 1, Nicolas

Lecture 14, Nov 8th, VC Dimension 2, Ricard

Lecture 15, Nov 10th, Isoperimetric Inequalities, Arkhadev

Lecture 16, Nov 15th, The Infamous upper tail, Erin

Lecture 17, Nov 17th, Hayward and Mcdiarmid, Concentration for Quicksort, Michal

Lecture 18, Nov 22nd, Vojkan

Lecture 19, Nov 24th, Vojkan

Lecture 20, Nov 29th, Vojkan

Lecture 21, Decmber 1st, Vojkan

Student presentations will begin on October 27th. The three lectures missed in September will be made up by having some of the student presentations on Fridays in November.