Randomized Algorithms

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 pdf
 Oct 1 Chernoff bounds, counting number of 0/1 knapsacks  pdf
 Oct 8 Clarkson’s algorithm for LPs, minimum enclosing balls pdf
Oct 15  Clarkson’s algorithm for LPs contd., Kalai-Kleitman diameter bound  pdf
 Oct 22 Schwarz-Zippel Lemma, Tutte polynomial and Maximum matchings in graphs  pdf
Oct 29  Lovasz Local Lemma and its applications, Moser’s algorithm for 3SAT pdf
Nov 5 Markov chains, Metropolis-Hastings algorithm pdf
Nov 12 The power method, probability ampilfication via random walks on expanders pdf
Nov 19 Rapidly mixing expander random walks, approximately solving a #P-complete problem pdf
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.