SPEAKER: Sebastian Pokutta

ABSTRACT:

Limits of system performance can often understood in the context of information and entropy. In the talk we give two examples. One theoretical one where a strong bound on the size of a smallest possible representation is obtained via an entropy argument. The second deals with an application where the goal is to eliminate information asymmetries using optimization methods.

More precisely:

In the first part, we solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem.

In the second part, we consider a real-world energy market coupling problem which aims for a more balanced and consistent determination of prices in adjacent markets in presence of coupling mechanisms. By doing so the amount of possible arbitrage is minimized.

(The first part is joined work with: Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf // the second part is joined work with: Alexander Martin and Johannes Müller)