Just like greedy algorithms, dynamic programming, or divide-and-conquer, the multiplicative weights method is a fundamental algorithmic technique with countless applications across disciplines. However, it is taught only rarely in basic classes.

In this class, we will study the multiplicative weights method in detail. We will learn about the basic technique and its variations, explore connections to other fields such as online convex optimization and machine learning, and see the beautiful mathematics that lies behind it.

We will also see many applications of the technique, with examples from combinatorial optimization, machine learning, algorithmic game theory, computational geometry, information theory, online algorithms, and many more. For some of the applications, we will have invited speakers who have applied the technique in their respective fields.

The class is jointly attended by students at Sorbonne Paris Nord in Paris and will be given in a hybrid format.

The course website can be found here: https://www.inf.fu-berlin.de/lehre/SS25/mwu/