Time: Tuesday and Thursday 3:00-4:30, Room: Biology 204.
Text: Randomized Algorithms by Motwani and Raghavan.
Other useful references:
- "Probability and Computing: Randomized Algorithms and Probabilitic Analysis," draft by Mitzenmacher and Upfal.
- Lecture notes by Avrim Blum at CMU.
- Lecture notes by David Karger at MIT.
-
Lecture notes by Anupam Gupta and Shuchi Chawla.
- ***** Note -- I've removed the orginal question number 2. Now you only have to do 5 out of 6 !!!*****
- Assigned Tuesday, November 23. Due December 7 (under my office door). ps.gz , pdf
Topics and links:
These links are meant to be a guideline and do not always mesh exactly with the lectures from class. Please send me updated references from your lectures if the ones I have are not the best.
- k-wise independence, linearity of expectation, quicksort
- Markov's inequality, Chebyshev's inequality, Chernoff bounds, complexity classes (See also this and this )
- Karger's min-cut algorithm
- Universal hashing
- Lower bounds, Spencer's graduation game
- Randomized rounding, probabilistic method
and
- The method of conditional probability and expectations
- Random walks and cover times
- Existence of expanders
- Amplifying randomness using random walks on expanders
- Expanders, eigenvalues and rapid mixing
- Approximate counting
- Randomly finding a perfect matching
- Approximating the permanent (part I)
- Approximating the permanent (part I)
- Approximately counting DNF assignments
- Lovasz local lemma
- Quantum computing and Shor's factoring algorithm
- Explicit construction of expanders
- Derandomization
- Computational geometry and backwards analysis
- Applications of Martingales
- For vertex exposal martingale,(p96) Alon and Spencer, The probabilistic method. Second edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
- For bin packing problem, (p477) Grimmett and Stirzaker, Probability and Random Processes (third edition), Oxford University Press, 2001
- Pseudo-random generators
- Goemans-Williamson randomized rounding and SDP
- Randomized primality testing
- Metric embeddings
Homework(s):
Presentations:
Tentative Schedule (and apologies for misspellings!!!!):
- Oct 12: Ramprasad Ravichandran -- Lovasz Local Lemma
- Oct 14: Tejas Iyer and Yi-An Huang -- Quantum computing and Shor's factoring algorithm
- Oct 21: Teena Carroll and Sam Greenberg -- Explicit construction of expanders
- Oct 26: Subrahmanyam Kalyanasundaram and David Cash -- Derandomization
- Oct 28: Subrahmanyam and David -- Derandomization (cont.)
- Nov 2: Jordy Eikenberry and Chris Henke -- Computational geometry and backwards analysis
- Nov 4: Torsten Inkmann and Sangho Shim -- Applications of Martingales
- Nov 9: Stephen Young and Fred Zahrn -- Pseudo-random generators
- Nov 11: Ken Chen and Michael White -- Randomized rounding
- Nov 16: Selin Caliskan and Sam Dambreville -- Primality testing
- Nov 18: Ashok Ponnuswami -- Metric Embeddings
- Nov 23: TBA
- Dec 2: TBA
Announcements:
Send me your preferences and partners by next weekend (Oct 1), even if it's tentative. I need a couple of brave souls to volunteer to speak next week and the week after that.
Here are some suggested topics. (Also look at topics in Motwani, Raghavan and Mitzenmacher, Upfal for alternative ideas more up your alley.) Several of these can be expanded to two lectures, so more than two people can work on a topic if you do a more in-depth presentation.
- Approximation scheme for Euclidean TSP (Arora/Mitchell)
- Analysis of local optimization algorithms (Aldous, Vazirani / Dimitriou-Impagliazzo)
- Overview of PCP and inapproximability (**maybe a larger group and 2 lectures)
- Pseudorandom number generators
- Explicit constructions of expanders
- Randomized rounding and semi-definite programming (Goemans, Williamson)
- Randomization in on-line algorithms (e.g., ski-rental, paging,...)
- On-line algorithms continued (the k-server problem)
- Metric embeddings (Linial, et al)
- Lovasz local lemma and applications
- Randomized primality testing
- Quantum computing and factoring (Shor)
- Derandomization (Luby, Widgerson notes on pairwise independence)
- Sublinear algorithms (e.g., Chazelle's MST alg)
- Computational geometry (e.g., randomized incremental algorithm for finding the convex hull)