Algorithms and Complexity

## Course description

In the course, we discuss modern algorithmic techniques. The course covers a variety of topics, such as for example:

• approximation algorithms
• randomized algorithms
• graph embeddings
• graph sparsification
• theory of learning
• sketching and streaming algorithms
• continuous methods in combinatorial optimization

There is no formal requirement, however some background in algorithm design/analysis and probability theory is expected. Having passed the algorithm theory course (or a similar course) prior to taking the advanced algorithms lecture is highly recommended.

## Schedule

• Lecture: Friday 10:00 - 12:00, Building 106 SR 00 007
• Exercise Class: Friday 12:00 - 14:00, Building 106 SR 00 007

## Exercises

There will be a weekly exercise sheet, which is published here. While exercise sheets are not graded, you can do it yourself and submit your solution to us and we will give you some feedback on it. This is recommended, but not mandatory (in order to take the exam). Solutions of the exercise sheet will be discussed in the following exercise class.

 Exercise sheet Assigned Solution Problem Set 01 (Set Cover, Integrality Gap) 26.04.2019 Sample Solution 01 Problem Set 02 (Chernoff Bounds) 03.05.2019 Sample Solution 02 Problem Set 03 (Probabilistic Tree Embeddings) 10.05.2019 Sample Solution 03 Problem Set 04 (Cut Based Tree Decompositions) 17.05.2019 Sample Solution 04 Problem Set 05 (Multiplicative Weight Updates) 27.05.2019 Sample Solution 05 Problem Set 06 (Learning Linear Classifiers with MWU) 31.05.2019 Sample Solution 06 Problem Set 07 (Max Flow, Zero Sum Games, MWU) 14.06.2019 Sample Solution 07 Problem Set 08 (Additive & Multipl. Spanners, APSP) 28.06.2019 Sample Solution 08 Problem Set 09 (Cuts, Sparsifiers) 05.07.2019 Sample Solution 09 Problem Set 10 (Max Flow, Cong. Approximators) 15.07.2019 Sample Solution 10 Problem Set 11 (Aggregation in the MPC Model) 23.07.2019 Sample Solution 11

## Lecture Material

All slides and recordings can be found on our Webserver.

## Literature

• A recording of the lecture on multiplicative weight updates by Ankur Moitra.
• The lecture on multiplicative weight updates exactly covers the material, which is described in Section 1, 2 , and 3.1 of a very nice survey on the topic by Arora, Hazan, and Kale.
• An application of the MWU algorithm for zero sum games.
• The web page of Ankur Moitras Course.