Vortragender: Prof. László Kozma (Freie Universität Berlin)

Algorithmic problems typically ask to transform each given input according to some well-defined mathematical function. For example, in the sorting problem, given a sequence of (comparable) items, we want to put them in increasing order.

When can we say that we fully understand the complexity of an algorithmic problem? Ideally, we should find an algorithm that solves the task in a certain number of elementary steps, and prove that no algorithm can achieve this in fewer steps. But how can we argue about all possible inputs and all possible algorithms, including those not yet invented? This basic question is behind some of the great mysteries of theoretical computer science; we have satisfactory answers only for relatively simple problems in restricted models of computation.

As a case study we will look at the problem of finding a saddle point, a task that arises both in optimization and game theory. Seemingly related to sorting, the problem allows for some surprising algorithmic improvements, with its precise complexity not yet settled.