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:

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