- Homework 3 posted. Due on December 4.
- Suggested list of course projects is available here. Please confirm your choice by October 23.
- Homework 2 posted. Due in the class on November 1.
- Homework 1 posted. Due in the class on September 11.
- First class on Monday, August 7 at 2:00pm in ECE 1.08

- Class: Monday and Wednesday 2pm-3:30pm in ECE 1.08

- Homework 3
**(due on December 4)** - Homework 2
**(due on November 1)** - Homework 1
**(due on September 11)**

- Lecture 1: Introduction to the course: Law of large numbers, central limit theorem (with Berry-Esseen correction), large deviation; Markov and Chebyshev inequalities; course overview; numerical evidence of concentration.
- Lecture 2: The Cramér-Chernoff method; properties of Cramér transform; Examples: Gaussian, Poisson, Bernoulli, Chi squared.
- Lecture 3: Sums of iid rvs; Application: Johnson-Lindenstrauss Lemma; sub-Gaussian rvs; variance of bounded rvs and Hoeffding inequality.
- Lecture 4: Concentration bounds for sums of iid: Hoeffding inequality (covered in lecture 3), Bennett inequality, Bernstein inequality, sum of mulitplicative family and Azuma's inequality; concentration for maximum of martingale noise; the bounded difference property and McDiarmid's inequality. [pdf]
- Lecture 5: Applications1: A bound on maximum of subGaussian random variables; longest common subsequence, chromatic number of Erdös-Rényi random graph; balls and bins setup -- number of empty bins. [pdf]
- Lecture 6: Applications2: Empirical process and uniform convergence; Glivenko-Cantelli Theorem; VC bound for deviation of empirical processes. [pdf]
- Lecture 7: Applications2: Chaining method to bound the deviation of empirical process; introduction of Efron-Stein inequality. [pdf]
- Lecture 8: The Efron-Stein inequality (contd.). [pdf]
- Lecture 9: Exponential concentration around median and mean via Efron-Stein; Gaussian Poincaré inequality [pdf]
- Lecture 10: Variance bound of self-bounding functions; Introduction to Entropy method: Herbst's argument. [pdf]
- Lecture 11: Subadditivity of entropy for discrete rvs; Variational formula for entropy; Gibbs variational principle. [pdf]
- Lecture 12 (short lecture): Subadditivity of entropy for general rvs; Introduction to Sobolev and log-Sobolev inequality; binary log-Sobolev inequality.
- Lecture 13: Gaussian log-Sobolev inequality; Gaussian concentration; concentration of supremum of Gaussian processes. [pdf]
- Lecture 14: A modified log-Sobolev inequality (valid for general rvs); Upper and lower tail bounds via entropy method; upper tail bound for weakly self-bounding functions. [pdf]
- Lecture 15: Lower tail bound for weakly self-bounding functions. [pdf]
- Lecture 16: Lower tail bound proof (contd.); Review of the course till date; Introduction to the Threshold Phenomenon. [pdf]
- Lecture 17: Russo's Lemma; formalizing threshold phenomenon; a strengthening of log-Sobolev inequality. [pdf]
- Lecture 18: Threshold phenomenon for symmetric monotone sets. [pdf]
- Lecture 19: Classical isoperimetric theorem; Levy's inequalities (connection b/w concentration and isoperimetry). [pdf]
- Lecture 20: Bounded difference property and isoperimetry; Blowing-up lemma; Talagrand's convex distance inequality and Talagrand's concentration inequality. [pdf]
- Lecture 21: Proof of Talagrand's convex distance inquality; examples. [pdf]
- Lecture 22: Examples (contd.): Suprema of Rademacher processes; Introducetion to transportation cost inequalities and coupling. [pdf]
- Lecture 23: Tranportation lemma (connection between concentration and transportation cost inequality); McDiarmid inequality via transportation lemma; proof of Pinsker's inequality; Marton's transportation cost inequlity. [pdf]
- Lecture 24: Concentration of functions beyond those satisfying the bounded difference property [pdf]
- Lecture 25: Marton's conditional transportation cost inequality. [pdf]

- Introduction & motivation: Limit results and concentration bounds
- Chernoff bounds: Hoeffding’s inequality, Bennett’s inequality, Bernstein’s inequality
- Variance bounds: Efron-Stein inequality, Poinca ́re inequality
- The entropy method and bounded difference inequalities
- Log-Sobolev inequalities and hypercontractivity
- Isoperimetric inequalities (Talagrand's convex distance inequality)
- The transportation method
- Influences and threshold phenomena

Homework (2-4) | 60% |

Literature review (to be done in groups of size 2) | 30% |

Class Participation | 10% |