Randomized Algorithms (Graduate)

(2nd half of Advanced TCS II)

Spring 2012

Institute for Theoretical Computer Science, Institute for Interdisciplinary
Sciences, Tsinghua University

Instructor: Jian Li
(lijian83@mail.tsinghua.edu.cn)

(1st half is on "Derandomization
and Randomness in Computation" taught by Periklis A. Papakonstantinou)

Teaching assistant: Yuan Wen

¡¡

References:

- Randomized Algorithms by R. Motwani and P. Raghavan, Cambridge University Press, 1995
- Probability and Computing: Randomized Algorithms and Probabilistic
Analysis by

Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005 - The Probabilistic Method, Third Edition by N. Alon and J. H. Spencer, Wiley, 2008
- Concentration of Measure for the Analysis of Randomized Algorithms by D.
P. Dubhashi and A. Panconesi, Cambridge University Press, 2009.

¡¡

Time: Monday & Wednesday 1.30-3.05pm (2x45min each)

Classroom: FIT 1-222

Schedule:

Apr.16 | Randomized quick sort, A simple randomized algorithm for min-cut, Selection, An expected linear time algorithm for closest pair | ¡¡ |

Apr.18 | Karps's Probabilistic Recurrences, Bins and Balls (m=n, Coupon Collector, Load Balancing, Birthday Paradox, Power of Two Choices), Packet Routing (a simple bound without LLL) | ¡¡ |

Apr.23 | Derandomization using Conditional Expectation, k-wise independence, Discrepancy: a simple bound via random coloring, derandomization using pessimistic estimator, Spencer's six standard deviation theorem | ¡¡ |

Apr.25 | Spencer's six standard deviation theorem (cont.), Beck-Fiala's Rounding Theorem, Discrepancy of boxes in R^d, A very brief intro to SDP | ¡¡ |

Apr.30 | Class Canceled due to Labor's Day | ¡¡ |

May.5 | Bansal's Constructive Discrepancy via SDP £¨the hereditary disc result£©, Lovasz Local Lemma | Homework 1 (due May 14) (Pls find the hw in the online course system) |

May.7 | Lovasz Local Lemma, Applications (k-Sat, Independent set), Algorithmic Lovasz Local Lemma | ¡¡ |

May.9 | Packet Routing (the 2^O(log^* d) result via LLL)£¬ Monte Carlo Method, Counting DNF£¬ Estimating the expected length of MST for a set of random points | ¡¡ |

May.14 | Estimating the expected length of MST for a set of random points(cont.), Universal Hashing, Perfect Hashing, Fredman-Komlos-Szemeredi | Homework 2 (due May 23) |

May.16 | Mitochondrial Eve and Wright-Fisher Model, Isoperimetric inequality, Harper's theorem on Hamming Cube, Method of Bounded Difference, Talagrand distance | ¡¡ |

May.21 | Talagrand distance (cont.), Method of non-uniformly bounded difference, Stochastic Traveling Salesman, Concentration of Certifiable functions | ¡¡ |

May.23 | Approximation algorithms: Set Cover, Max cut on dense graphs | Homework 3 (due Jun 4) |

May.28 | Dependent Rounding, Thoughput maximization for broadcast scheduling, Johnson-Lindenstrauss | ¡¡ |

May.30 | Johnson-Lindenstrauss (Cont.), Probabilistic embedding into trees (Fakcharoenphol-Rao-Talwar) | ¡¡ |

Jun.4 | Locality Sensitive Hashing (via stable distribution), Solutions of some hw problems. | ¡¡ |

Jun.6 | Final Exam (3 hours) | ¡¡ |

Jun.15 | ¡¡ | Project Due |