TITLE:  Information and Entropy

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)