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


Time: Monday & Wednesday 1.30-3.05pm (2x45min each)
Classroom: FIT 1-222


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