ATCSII-Randomized Algorithm 2012Spring IIIS

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