CSL857: Lecture Notes

  • January 03: Introduction

  • January 04: Introduction (Linearity of expectation, Markov, Chebychev, Coupon collector, Birthday problem etc.)

  • January 09: Birthday problem, Karger's Min-cut algorithm.

  • January 12: Karger's Min-cut algorithm, Randomized Complexity classes.

  • January 16: Randomized Complexity Classes, Chernoff bounds.

  • January 19: Chernoff bounds, Balls and Bins, Power of two choices.

  • January 23: Power of two choices, Lovasz Local Lemma(LLL).

  • January 30: Lovasz Local Lemma(LLL).

  • February 2: Lovasz Local Lemma.
    • Minor-I: 4th February (Problems)(Answers)

  • February 09: Constructive LLL

  • February 13: Hash Functions

  • February 16: Martingales (Introduction, Stopping Theorem)

  • February 21: Martingales (Stopping Theorem, Azuma Hoeffding)

  • February 23: Martingales (Doob Martingales)

  • February 27: Routing in a Hypercube

  • March 1: Routing in a Hypercube

  • March 15: Markov Chains & Random Walks

  • March 19: Markov Chains & Random Walks
    • Minor-II: 23rd March (Problems)(Answers)

  • March 26: The Monte Carlo Method (DNF counting)

  • March 29: The Monte Carlo Method (Counting Independent Sets)

  • April 2: Monte Carlo Markov Chain (MCMC), Metropolis Algorithm.

  • April 9: Coupling

  • April 16: Coupling

  • April 19: Spectral Analysis of graphs.

  • April 23: Expanders, Probability amplification using expanders.

  • April 26: Probability amplification using expanders.

  • April 30: Johnson Lindenstrauss Lemma
    • Major: 4th May(Fri) (Take-home Major (Deadline: 10th May(5PM)))