Course Schedule, Winter 2012
| Date | Lecture |
|---|---|
| Lecture 1: January 10 | Introduction to course; Amplification |
| Lecture 2: January 12 | Amplification. Notes for lectures 1 & 2 by Mark Kempton |
| Lecture 3: January 17 | Load Balancing. Notes for lecture 3 by Olivia Simpson |
| Lecture 4: January 19 | Skip Lists, Randomization, and Quicksort. Notes for lecture 4 by Fletcher Smith |
| Lecture 5: January 24 | |
| Lecture 6: January 26 | Low Distortion Embeddings. Notes for lecture 6 by Ariel Levavi |
| Lecture 7: January 31 | Probabilistic Recurrences. Notes for lecture 7 by Jeffery Truman |
| Lecture 8: February 2 | Presentation: Andy Wilson, Growing Protean Graphs by P. Pralat and N. Wormald. Notes from the lecture are posted here. |
| Lecture 9: February 7 | Lecture by Stephen Young. Lovasz Local Lemma. Notes from lecture 7 by Daniel Ricketts. |
| Lecture 10: February 9 | Presentation: Mark Kempton, The spectra of random graphs with given expected degrees by F. Chung, L. Lu, and V. Vu. Completion of Stephen Young's lecture on the Algorithmic Local Lemma. Notes from the lecture written by Michael Tait can be found here. |
| Lecture 11: February 14 | Presentation: Jay Cummings, Cops and Robbers on Geometric Graphs by A. Beveridge, A. Dudek, A. Frieze, and T. Mueller |
| Lecture 12: February 16 | Martingales. Notes for lecture 12 by Andy Wilson. Presentation: Christian Woods, Graphs with Integral Spectrum by O. Ahmadi, N. Alon, I.F. Blake, and I.E. Shparlinski |
| Lecture 13: February 21 | Martingales. Notes for lecture 13 by Mark Kempton |
| Lecture 14: February 23 | Presentation: Jeffrey Truman, Birth control for giants by J. Spencer and N. Wormald |
| Lecture 15: February 28 | Presentation: Daniel Ricketts, On smoothed analysis in dense graphs and formulas by M. Krivelaich, B. Sudakov, and P. Tetali |
| Lecture 16: March 1 | Presentation: Mike Tait, Enumeration of Cospectral Graphs by W. Haemers and E. Spence |
| Lecture 17: March 6 | Presentation: Fletcher Smith, Increasing the Chromatic Number of Random Graph by N. Alon and B. Sudakov; Olivia Simpson, Expansion properties of a random regular graph after random vertex deletion by C.S. Greenhill, F.B. Holt, and N. Wormald |
| Lecture 18: March 8 | Presentation: Anurag Narra, Random graphs with a given degree sequence by S. Chatterjee, P. Diaconis, and A. Sly |
| Lecture 19: March 13 | Presentation: Benji Greenberg, Periodic Graphs by C. Godsil; Jeffrey Truman's follow-up. |
| Lecture 20: March 15 | Steve Young will lecture on FKG inequality and concentrations for one-sided Martigales.
Lecture notes by Olivia.
Presentation: Joonleng Tan, Asymptotic packing and the random greedy algorithm by V. Rodl and L. Thoma. Here is Joonleng's notes. |