to be informed

We explore a two-dimensional "world" which has one axis for algorithmic methods and a second axis for models of computation. This world is explored by considering canonic problems such as maximum matching, minimum vertex cover, maximal independent set, and packing and covering. The axis of algorithmic methods consists of greedy selection, augmenting paths, primal-dual, and multiplicative weights. The models of computation are: the standard sequential model, distributed algorithms (LOCAL and CONGEST models), sublinear algorithms, online algorithms, and online learning.
Each model of computation is characterized by a dierent constraint that limits the algorithm designer. For example: in online algorithms, irrevocable decisions must be made before the whole input is revealed; in sublinear algorithms, decisions must be made based on seeing only a small fraction of the input; in distributed algorithms, decisions must be made based only on local information.
Overcoming these challenges often requires one to resort to approximate solutions. For example, instead of computing a maximum matching, we are satis ed with a matching, the cardinality of which at least (1 - ¿) times the maximum cardinality matching. Randomization is often employed to cope with partial information.

This is a visiting professor course of the Vienna PhD School of Informatics.

It will be held by Guy Even, Tel-Aviv University.

The course will be held as blocked course.

Please register in TISS.