| Date: | Tues and Thurs, 9:30-11:00 AM |
| Room: | Cooll. of Computing 52 |
| Instructor: | Juan Vera |
| Office hours: | Tues and Thurs, 11 - 12 or by appointment. Klaus 2113 |
This course teaches techniques for the design and analysis of randomized algorithms. The course is based on the book Randomized Algorithms by Motwani and Raghavan (Cambridge University Press, 1995), Lecture's notes (mainly Eric Vigoda's) and selected papers.
There will be 3 homework (25% each), a final presentation (20%) and scribing (5%).
| Jan 9 | Introduction: Some toy examples | Notes Chapter 1.1-1.4 |
| Jan 11 | Karger's Min-cut algorithm | Eric's notes; [Karger] and improvement of [Karger/Stein] Chapter 10.2 |
| Jan 16 | Moments and deviations: Coupon collector's problem. | Notes. Chapter 3 |
| Jan 18 | Review of Chernoff Bounds. | Notes. Chapter 4 |
| Related project idea | Improved deviation bounds by [Kim/Vu],[Vu] | |
| Jan 23 | No Class | Workshop on Complex Networks and Their Applications. Jan 22-24 |
| Jan 25 | #DNF and Network Unreliability | Eric's notes;
[Karger] Chapter 11.2 has a different approach for #DNF. |
| Related project idea | Deterministic approximation of #DNF in O(exp(log4n)) time [Luby/Velickovic/Wigderson] | |
| Jan 30 | Balls and Bins, power of 2 choices | Eric's notes |
| Related project idea |
Improved power of 2 choices
[Vocking]
Many more balls than bins [Berenbrink et al] |
|
| Feb. 1 | Probabilistic Method | Chapter 5.1-5.2, 5.5 |
| Feb. 6 | Hypergraph 2-coloring, aka Property B | Eric's notes; [Radhakrishnan/Srinivasan] |
| Feb. 8 | De-randomization: Conditional Expectation and Pairwise Independence | Notes. Chapter 5.6 See Chapters 6.1-6.3 and 13.1 of [Mitz/Upfal] |
| Feb. 13 | Application of Pairwise Independence: Maximal Independent Sets | Eric's notes See notes by Luby and Wigderson for some complexity applications of pairwise independence. |
| Feb. 15 | Hash Functions | Chapters 8.4 -8.5 |
| Feb. 20 | Sampling and Counting Relationship: Approximating #Knapsack | Eric's notes; [Dyer]'s original paper |
| Feb. 22 | Random walks and cover times. Resistive Networks | Chapters 6.1, 6.3-6.5 |
| Feb. 27 | Markov chains; Ergodic -> Unique stationary distribution | Eric's notes |
| Mar. 1-6 | Coupling method for analyzing Markov chains | Eric's notes |
| Mar 13 | Probability amplification by random walks on expanders | Chapters 5.3, 6.7, 6.8 Notes from class by by Linial and Wigderson on expander graphs |
| Mar 15 | Approximating the permanent | Eric's notes; See this chapter by Jerrum (especially Section 5.3) . |
| Mar 20-22 | Spring Break | Workshop on Phase transitions in Random Structures and Algorithms |
| Mar 27 | No class | Working Group on current topics in Markov Chains on phase transitions |
| Mar 29 | Primality testing. | Chapter 14.6 |
| April 2-4 | The Preferential Attachment Graph. | Notes from Alan Frieze's class. |
| Student Presentations | ||
| April 10 | Deterministic Amplification and Pseudorandomness | Kintali S. Prasad & Akshay Wadia |
| April 12 | LT Codes | Ting Wang |
| Maximum Independent Set in a Sparse Random Graph | Varun N. Kanade | |
| April 17 | Semidefinite Approximation for Max-Cut | Yao H. Chen |
| Multilevel Schemes for Graph Partitioning | Murat E. Guney | |
| April 19 | Sampling Uniform Colorings on Planar Graphs | Amanda M. Pascoe |
| Cover Time for Some Random Models of Graphs | Carl R. Yerger | |
| April 24 | Craig C. Cambias | |
| Chinmay D. Karande |
Text: Randomized Algorithms by Rajeev Motani and Prabhakar Raghavan.
The Probabilistic Method by Noga Alon and Joel Spencer is a nice related book.
Probability and Computing by Michael Mitzenmacher and Eli Upfal might be useful, especially if you want extra background material.