Logistics
Course description: Randomness is an important and powerful resource that the algorithm designer has at her disposal. Indeed, one of the major unsolved problems in computer science is to understand the power of randomness in the design of efficient algorithms. In this course we will take a tour through the rich variety of randomized algorithms that have been used to solve classical problems in combinatorial optimization. Specific examples include approximating min/max cuts in graphs, finding perfect matchings, finding satisfying assignments for some classes of k-SAT formulae, etc. For an approximate overview of the course contents have a look at the previous edition of this course.
This time we will also have a special focus on linear programming. If time permits we will also discuss volume estimation of convex bodies, where randomness is provably essential.
Instructor: Prof. Friedrich Eisenbrand
Assistant: Chidambaram Annamalai
Language: English
ECTS credits: 4
Lecture: Wednesdays from 9:30AM to 11:30AM at MA B1 524 (Coffee room)
Exercise Sessions: Cancelled. Instead if you questions or would like hints then please send Chidambaram a mail with what you tried. You are also allowed to collaborate (upto three people in total) but return separate solutions.
Important notes:
- Please try to send the scribe notes within a week from the lecture ! Make sure to send the tex files with the pdf.
- The deadline for submitting solutions to the fourth problem set is Dec 17 23:59 CET.
- Use the preamble.tex file to scribe lectures (example) and return solutions to problem sets (example)
- Send your solutions in pdf (typeset in latex) to the main assistant
Problem sets
| Deadline | Problem set | Solution |
| Oct 8 | Problem Set 1 | |
| Oct 22 | Problem Set 2 | |
| Nov 12 | Problem Set 3 | |
| Dec 17 | Problem Set 4 |
Lectures
| Date | Lecture | Scribe Notes |
| Sep 17 | — | — |
| Sep 24 | Mincuts, linear programming, volume estimation | |
| Oct 1 | Chernoff bounds, counting number of 0/1 knapsacks | |
| Oct 8 | Clarkson’s algorithm for LPs, minimum enclosing balls | |
| Oct 15 | Clarkson’s algorithm for LPs contd., Kalai-Kleitman diameter bound | |
| Oct 22 | Schwarz-Zippel Lemma, Tutte polynomial and Maximum matchings in graphs | |
| Oct 29 | Lovasz Local Lemma and its applications, Moser’s algorithm for 3SAT | |
| Nov 5 | Markov chains, Metropolis-Hastings algorithm | |
| Nov 12 | The power method, probability ampilfication via random walks on expanders | |
| Nov 19 | Rapidly mixing expander random walks, approximately solving a #P-complete problem | |
| Nov 26 | Cheeger’s inequality and a spectral partitioning algorithm | ext. notes |
| Dec 3 | Randomized primality testing | — |
| Dec 10 | Benczur-Karger graph sparsifiers | ext. notes |
| Dec 17 | Approximating the largest subdeterminant | ext. paper |
Grading
Your final grade will be based on your performance in
- problem sets,
- scribe notes, and
- an oral exam.
Books and references
Randomized Algorithms. Rajeev Motwani and Prabhakar Raghavan. ISBN 0-521-47465-5.
Probability and Computing. Michael Mitzenmacher and Eli Upfal. ISBN 978-0-521-83540-4.
The Probabilistic Method. Alon, Noga; Spencer, Joel H. (2000). ISBN 0-471-37046-0.